Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process

Metaheurística GRASP para o problema de planejamento da expansão de sistemas de transmissão de energia elétrica

Pós-graduação em Engenharia Elétrica - FEIS

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

Modelo estocástico de programação matemática de alocação de medidores de tensão em alimentadores radiais de distribuição de energia elétrica para localização de faltas e monitoramento do perfil de tensão

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Fluxo de carga não-iterativo para a análise de sistemas de distribuição de energia elétrica radiais e malhados

Pós-graduação em Engenharia Elétrica - FEIS

Reconfiguração de alimentadores em sistemas de distribuição usando a metaheurística GRASP

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Algoritmo GRASP especializado aplicado ao problema de reconfiguração de alimentadores em sistemas de distribuição radial

Pós-graduação em Engenharia Elétrica - FEIS

GRASP and statistical bounds for heuristic solutions to combinatorial problems

The quality of a heuristic solution to a NP-hard combinatorial problem is hard to assess. A few studies have advocated and tested statistical bounds as a method for assessment. These studies indicate that statistical bounds are superior to the more widely known and used deterministic bounds. However, the previous studies have been limited to a few metaheuristics and combinatorial problems and, hence, the general performance of statistical bounds in combinatorial optimization remains an open question. This work complements the existing literature on statistical bounds by testing them on the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP) and four combinatorial problems. Our findings confirm previous results that statistical bounds are reliable for the p-median problem, while we note that they also seem reliable for the set covering problem. For the quadratic assignment problem, the statistical bounds has previously been found reliable when obtained from the Genetic algorithm whereas in this work they found less reliable. Finally, we provide statistical bounds to four 2-path network design problem instances for which the optimum is currently unknown.

The preparation of reach to grasp movements in adults with Down syndrome

The aim of this study was to determine the extent to which adults with Down syndrome (DS) are able to utilise advance information to prepare reach to grasp movements. The study comprised ten adults with DS; ten children matched to an individual in the group with DS on the basis of their intellectual ability, and twelve adult controls. The participants used their right hand to reach out and grasp illuminated perspex blocks. Four target blocks were positioned on a table surface, two to each side of the midsagittal plane. In the complete precue condition, participants were provided with information specifying the location of the target. In the partial precue condition, participants were given advance information indicating the location of the object relative to the midsagittal plane (left or right). In the null condition, advance information concerning the position of the target object was entirely ambiguous. It was found that both reaction times and movement times were greater for the participants with DS than for the adults without DS. The reaction times exhibited by individuals with DS in the complete precue condition were lower than those observed in the null condition, indicating that they had utilised advance information to prepare their movements. In the group with DS, when advance information specified only the location of the target object relative to the midline, reaction times were equivalent to those obtained when ambiguous information was given. In contrast, the adults without DS exhibited reaction times that were lower in both the complete and partial precue conditions when compared to the null condition. The pattern of results exhibited by the children was similar to that of the adults without DS. The movement times exhibited by all groups were not influenced by the precue condition. In summary, our findings indicate that individuals with DS are able to use advance information if it specifies precisely the location of the target object in order to prepare a reach to grasp movement. The group with DS were unable, however, to obtain the normal advantage of advance information specifying only one dimension of the movement goal (i.e., the position of an object relative to the body midline). (C) 2001 Elsevier Science B.V. All rights reserved.

The effect of obstacle position on reach-to-grasp movements

Numerous everyday tasks require the nervous system to program a prehensile movement towards a target object positioned in a cluttered environment. Adult humans are extremely proficient in avoiding contact with any non-target objects (obstacles) whilst carrying out such movements. A number of recent studies have highlighted the importance of considering the control of reach-to-grasp (prehension) movements in the presence of such obstacles. The current study was constructed with the aim of beginning the task of studying the relative impact on prehension as the position of obstacles is varied within the workspace. The experimental design ensured that the obstacles were positioned within the workspace in locations where they did not interfere physically with the path taken by the hand when no obstacle was present. In all positions, the presence of an obstacle caused the hand to slow down and the maximum grip aperture to decrease. Nonetheless, the effect of the obstacle varied according to its position within the workspace. In the situation where an obstacle was located a small distance to the right of a target object, the obstacle showed a large effect on maximum grip aperture but a relatively small effect on movement time. In contrast, an object positioned in front and to the right of a target object had a large effect on movement speed but a relatively small effect on maximum grip aperture. It was found that the presence of two obstacles caused the system to decrease further the movement speed and maximum grip aperture. The position of the two obstacles dictated the extent to which their presence affected the movement parameters. These results show that the antic ipated likelihood of a collision with potential obstacles affects the planning of movement duration and maximum grip aperture in prehension.

Simulated annealing metaheuristic to solve the optimal power flow

The optimal power flow problem has been widely studied in order to improve power systems operation and planning. For real power systems, the problem is formulated as a non-linear and as a large combinatorial problem. The first approaches used to solve this problem were based on mathematical methods which required huge computational efforts. Lately, artificial intelligence techniques, such as metaheuristics based on biological processes, were adopted. Metaheuristics require lower computational resources, which is a clear advantage for addressing the problem in large power systems. This paper proposes a methodology to solve optimal power flow on economic dispatch context using a Simulated Annealing algorithm inspired on the cooling temperature process seen in metallurgy. The main contribution of the proposed method is the specific neighborhood generation according to the optimal power flow problem characteristics. The proposed methodology has been tested with IEEE 6 bus and 30 bus networks. The obtained results are compared with other wellknown methodologies presented in the literature, showing the effectiveness of the proposed method.

Metaheuristic approach to the Holt-Winters optimal short term load forecast

Electricity short-term load forecast is very important for the operation of power systems. In this work a classical exponential smoothing model, the Holt-Winters with double seasonality was used to test for accurate predictions applied to the Portuguese demand time series. Some metaheuristic algorithms for the optimal selection of the smoothing parameters of the Holt-Winters forecast function were used and the results after testing in the time series showed little differences among methods, so the use of the simple local search algorithms is recommended as they are easier to implement.

Representation of motor habit in a sequence of repetitive reach and grasp movements performed by macaque monkeys: evidence for a contribution of the dorsolateral prefrontal cortex.

In the context of an autologous cell transplantation study, a unilateral biopsy of cortical tissue was surgically performed from the right dorsolateral prefrontal cortex (dlPFC) in two intact adult macaque monkeys (dlPFC lesioned group), together with the implantation of a chronic chamber providing access to the left motor cortex. Three other monkeys were subjected to the same chronic chamber implantation, but without dlPFC biopsy (control group). All monkeys were initially trained to perform sequential manual dexterity tasks, requiring precision grip. The motor performance and the prehension's sequence (temporal order to grasp pellets from different spatial locations) were analysed for each hand. Following the surgery, transient and moderate deficits of manual dexterity per se occurred in both groups, indicating that they were not due to the dlPFC lesion (most likely related to the recording chamber implantation and/or general anaesthesia/medication). In contrast, changes of motor habit were observed for the sequential order of grasping in the two monkeys with dlPFC lesion only. The changes were more prominent in the monkey subjected to the largest lesion, supporting the notion of a specific effect of the dlPFC lesion on the motor habit of the monkeys. These observations are reminiscent of previous studies using conditional tasks with delay that have proposed a specialization of the dlPFC for visuo-spatial working memory, except that this is in a different context of "free-will", non-conditional manual dexterity task, without a component of working memory.

Effects of unilateral motor cortex lesion on ipsilesional hand's reach and grasp performance in monkeys: relationship with recovery in the contralesional hand.

Manual dexterity, a prerogative of primates, is under the control of the corticospinal (CS) tract. Because 90-95% of CS axons decussate, it is assumed that this control is exerted essentially on the contralateral hand. Consistently, unilateral lesion of the hand representation in the motor cortex is followed by a complete loss of dexterity of the contralesional hand. During the months following lesion, spontaneous recovery of manual dexterity takes place to a highly variable extent across subjects, although largely incomplete. In the present study, we tested the hypothesis that after a significant postlesion period, manual performance in the ipsilesional hand is correlated with the extent of functional recovery in the contralesional hand. To this aim, ten adult macaque monkeys were subjected to permanent unilateral motor cortex lesion. Monkeys' manual performance was assessed for each hand during several months postlesion, using our standard behavioral test (modified Brinkman board task) that provides a quantitative measure of reach and grasp ability. The ipsilesional hand's performance was found to be significantly enhanced over the long term (100-300 days postlesion) in six of ten monkeys, with the six exhibiting the best, though incomplete, recovery of the contralesional hand. There was a statistically significant correlation (r = 0.932; P < 0.001) between performance in the ipsilesional hand after significant postlesion period and the extent of recovery of the contralesional hand. This observation is interpreted in terms of different possible mechanisms of recovery, dependent on the recruitment of motor areas in the lesioned and/or intact hemispheres.

Intelligent task-level grasp mapping for robot control

In the future, robots will enter our everyday lives to help us with various tasks.For a complete integration and cooperation with humans, these robots needto be able to acquire new skills. Sensor capabilities for navigation in real humanenvironments and intelligent interaction with humans are some of the keychallenges.Learning by demonstration systems focus on the problem of human robotinteraction, and let the human teach the robot by demonstrating the task usinghis own hands. In this thesis, we present a solution to a subproblem within thelearning by demonstration field, namely human-robot grasp mapping. Robotgrasping of objects in a home or office environment is challenging problem.Programming by demonstration systems, can give important skills for aidingthe robot in the grasping task.The thesis presents two techniques for human-robot grasp mapping, directrobot imitation from human demonstrator and intelligent grasp imitation. Inintelligent grasp mapping, the robot takes the size and shape of the object intoconsideration, while for direct mapping, only the pose of the human hand isavailable.These are evaluated in a simulated environment on several robot platforms.The results show that knowing the object shape and size for a grasping taskimproves the robot precision and performance