Multi-criteria optimization manipulator trajectory planning

In the last twenty years genetic algorithms (GAs) were applied in a plethora of fields such as: control, system identification, robotics, planning and scheduling, image processing, and pattern and speech recognition (Bäck et al., 1997). In robotics the problems of trajectory planning, collision avoidance and manipulator structure design considering a single criteria has been solved using several techniques (Alander, 2003). Most engineering applications require the optimization of several criteria simultaneously. Often the problems are complex, include discrete and continuous variables and there is no prior knowledge about the search space. These kind of problems are very more complex, since they consider multiple design criteria simultaneously within the optimization procedure. This is known as a multi-criteria (or multiobjective) optimization, that has been addressed successfully through GAs (Deb, 2001). The overall aim of multi-criteria evolutionary algorithms is to achieve a set of non-dominated optimal solutions known as Pareto front. At the end of the optimization procedure, instead of a single optimal (or near optimal) solution, the decision maker can select a solution from the Pareto front. Some of the key issues in multi-criteria GAs are: i) the number of objectives, ii) to obtain a Pareto front as wide as possible and iii) to achieve a Pareto front uniformly spread. Indeed, multi-objective techniques using GAs have been increasing in relevance as a research area. In 1989, Goldberg suggested the use of a GA to solve multi-objective problems and since then other researchers have been developing new methods, such as the multi-objective genetic algorithm (MOGA) (Fonseca & Fleming, 1995), the non-dominated sorted genetic algorithm (NSGA) (Deb, 2001), and the niched Pareto genetic algorithm (NPGA) (Horn et al., 1994), among several other variants (Coello, 1998). In this work the trajectory planning problem considers: i) robots with 2 and 3 degrees of freedom (dof ), ii) the inclusion of obstacles in the workspace and iii) up to five criteria that are used to qualify the evolving trajectory, namely the: joint traveling distance, joint velocity, end effector / Cartesian distance, end effector / Cartesian velocity and energy involved. These criteria are used to minimize the joint and end effector traveled distance, trajectory ripple and energy required by the manipulator to reach at destination point. Bearing this ideas in mind, the paper addresses the planning of robot trajectories, meaning the development of an algorithm to find a continuous motion that takes the manipulator from a given starting configuration up to a desired end position without colliding with any obstacle in the workspace. The chapter is organized as follows. Section 2 describes the trajectory planning and several approaches proposed in the literature. Section 3 formulates the problem, namely the representation adopted to solve the trajectory planning and the objectives considered in the optimization. Section 4 studies the algorithm convergence. Section 5 studies a 2R manipulator (i.e., a robot with two rotational joints/links) when the optimization trajectory considers two and five objectives. Sections 6 and 7 show the results for the 3R redundant manipulator with five goals and for other complementary experiments are described, respectively. Finally, section 8 draws the main conclusions.

Fitness function evaluation through fractional algorithms

This paper proposes a Genetic Algorithm (GA) for the design of combinational logic circuits. The fitness function evaluation is calculated using Fractional Calculus. This approach extends the classical fitness function by including a fractional-order dynamical evaluation. The experiments reveal superior results when comparing with the classical method.

Automated design of microwave discrete tuning differential capacitance circuits in Si-integrated technologies

A genetic algorithm used to design radio-frequency binary-weighted differential switched capacitor arrays (RFDSCAs) is presented in this article. The algorithm provides a set of circuits all having the same maximum performance. This article also describes the design, implementation, and measurements results of a 0.25 lm BiCMOS 3-bit RFDSCA. The experimental results show that the circuit presents the expected performance up to 40 GHz. The similarity between the evolutionary solutions, circuit simulations, and measured results indicates that the genetic synthesis method is a very useful tool for designing optimum performance RFDSCAs.

A fractional calculus perspective in the evolutionary design of combinational circuits

This paper analyses the performance of a genetic algorithm (GA) in the synthesis of digital circuits using two novel approaches. The first concept consists in improving the static fitness function by including a discontinuity evaluation. The measure of variability in the error of the Boolean table has similarities with the function continuity issue in classical calculus. The second concept extends the static fitness by introducing a fractional-order dynamical evaluation.

Análise dinâmica de composições musicais

A composição musical é um tema de muito interesse para a computação evolucionária dentro da área da inteligência artificial. É uma área que tem sofrido vários desenvolvimentos ao longo dos últimos anos pois o interesse em que hajam computadores que façam obras musicais é deveras aliciante. Este trabalho tem por objectivo realizar mais um passo nesse sentido. Assim, foi desenvolvida uma aplicação informática que realiza composições musicais de dois géneros distintos: Músicas Infantis e Músicas Blues. A aplicação foi implementada com recurso aos Algoritmos Genéticos, que são os algoritmos evolucionários mais populares da área da computação evolucionária. O trabalho foi estruturado em duas fases de desenvolvimento. Na primeira fase, realizou-se um levantamento estatístico sobre as características específicas de cada um dos géneros musicais. Analisaram-se quinze músicas de cada género musical, com o intuito de se chegar a uma proporção do uso que cada nota tem em cada um dos casos. Na segunda fase, desenvolveu-se o software que compõe as músicas com implementação de um algoritmo genético. Além disso, foi também desenvolvida uma interface gráfica que permite ao utilizador a escolha do género musical que pretende compor. O algoritmo genético começa por gerar uma população inicial de potenciais soluções de acordo com a escolha do utilizador, realizando, de seguida, o ciclo que caracteriza o algoritmo genético. A população inicial é constituída por soluções que seguem as regras que foram implementadas de acordo com os dados recolhidos ao longo da primeira fase. Foi também implementada uma interface de avaliação, através da qual, o utilizador pode ouvir cada uma das músicas para posterior avaliação em termos de fitness. O estado de evolução do algoritmo é apresentado, numa segunda interface, a qual facilita a clareza e justiça na avaliação ao longo de todo o processo. Esta última apresenta informação sobre a média das fitness da geração anterior e actual, sendo assim possível ter uma noção da evolução do algoritmo, no sentido de se obterem resultados satisfatórios no que diz respeito às composições musicais.

Modeling Vegetable Fractals by means of Fractional-order Equations

This paper characterizes four ‘fractal vegetables’: (i) cauliflower (brassica oleracea var. Botrytis); (ii) broccoli (brassica oleracea var. italica); (iii) round cabbage (brassica oleracea var. capitata) and (iv) Brussels sprout (brassica oleracea var. gemmifera), by means of electrical impedance spectroscopy and fractional calculus tools. Experimental data is approximated using fractional-order models and the corresponding parameters are determined with a genetic algorithm. The Havriliak-Negami five-parameter model fits well into the data, demonstrating that classical formulae can constitute simple and reliable models to characterize biological structures.

A Fractional Calculus Perspective in the Evolutionary Design of Combinational Circuits

This paper analyses the performance of a genetic algorithm (GA) in the synthesis of digital circuits using two novel approaches. The first concept consists in improving the static fitness function by including a discontinuity evaluation. The measure of variability in the error of the Boolean table has similarities with the function continuity issue in classical calculus. The second concept extends the static fitness by introducing a fractional-order dynamical evaluation.

A Real-Time Optimization for 2R Manipulators

This work proposes a real-time algorithm to generate a trajectory for a 2 link planar robotic manipulator. The objective is to minimize the space/time ripple and the energy requirements or the time duration in the robot trajectories. The proposed method uses an off line genetic algorithm to calculate every possible trajectory between all cells of the workspace grid. The resultant trajectories are saved in several trees. Then any trajectory requested is constructed in real-time, from these trees. The article presents the results for several experiments.

Algoritmo genético para empacotamento de contentores

No âmbito da investigação operacional o problema de empacotamento de contentores é conhecido por procurar definir uma configuração de carga, de forma a otimizar a utilização de um espaço disponível para efetuar o empacotamento. Este problema pode ser apresentado em diversas formas, formas estas que variam em função das características de cada empacotamento. Estas características podem ser: o tipo de carga que se pretende carregar (homogénea ou heterogénea), a possibilidade de a carga poder sofrer rotações em todas as suas dimensões ou apenas em algumas, o lucro que está associado a cada caixa carregada ou restrições inerentes ao contentor como por exemplo dimensões. O interesse pelo estudo de problemas de empacotamento de contentores tem vindo a receber cada vez mais ênfase por várias razões, uma delas é o interesse financeiro dado que o transporte é uma prática que representa custos, sendo importante diminuir estes custos aproveitando o volume do contentor da melhor forma. Outra preocupação que motiva o estudo deste problema prende-se com fatores ambientes, onde se procura racionalizar os recursos naturais estando esta também ligada a questões financeiras. Na literatura podem ser encontradas varias propostas para solucionar este problema, cada uma destas dirigidas a uma variante do problema, estas propostas podem ser determinísticas ou não determinísticas onde utilizam heurísticas ou metaheurísticas. O estudo realizado nesta dissertação descreve algumas destas propostas, nomeadamente as metaheurísticas que são utilizadas na resolução deste problema. O trabalho aqui apresentado traz também uma nova metaheurísticas, mais precisamente um algoritmo genético que terá como objetivo, apresentar uma configuração de carga para um problema de empacotamento de um contentor. O algoritmo genético tem como objetivo a resolução do seguinte problema: empacotar várias caixas retangulares com diversos tamanhos num contentor. Este problema é conhecido como Bin-Packing. A novidade que este algoritmo genético vai introduzir nas diversas soluções apresentadas até à data, é uma nova forma de criar padrões iniciais, ou seja, é utilizada a heurística HSSI (Heurística de Suavização de Superfícies Irregulares) que tem como objetivo criar uma população inicial de forma a otimizar o algoritmo genético. A heurística HSSI tenta resolver problemas de empacotamento simulando, o comportamento da maioria das pessoas ao fazer este processo na vida real, contudo, tem um campo de busca reduzido entre as soluções possíveis e será então utilizado um algoritmo genético para ampliar este campo de busca e explorar novas soluções. No final pretende-se obter um software onde será possível configurar um dado problema de empacotamento de um contentor e obter, a solução do mesmo através do algoritmo genético. Assim sendo, o estudo realizado tem como principal objetivo contribuir com pesquisas e conclusões, sobre este problema e trazer uma nova proposta de solução para o problema de empacotamento de contentores.

Crossing genetic and swarm intelligence algorithms to generate logic circuits

Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetic. The basic concept of GAs is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest. On the other hand, Particle swarm optimization (PSO) is a population based stochastic optimization technique inspired by social behavior of bird flocking or fish schooling. PSO shares many similarities with evolutionary computation techniques such as GAs. The system is initialized with a population of random solutions and searches for optima by updating generations. However, unlike GA, PSO has no evolution operators such as crossover and mutation. In PSO, the potential solutions, called particles, fly through the problem space by following the current optimum particles. PSO is attractive because there are few parameters to adjust. This paper presents hybridization between a GA algorithm and a PSO algorithm (crossing the two algorithms). The resulting algorithm is applied to the synthesis of combinational logic circuits. With this combination is possible to take advantage of the best features of each particular algorithm.

Adaptive Penalty and Barrier function based on Fuzzy Logic

Optimization methods have been used in many areas of knowledge, such as Engineering, Statistics, Chemistry, among others, to solve optimization problems. In many cases it is not possible to use derivative methods, due to the characteristics of the problem to be solved and/or its constraints, for example if the involved functions are non-smooth and/or their derivatives are not know. To solve this type of problems a Java based API has been implemented, which includes only derivative-free optimization methods, and that can be used to solve both constrained and unconstrained problems. For solving constrained problems, the classic Penalty and Barrier functions were included in the API. In this paper a new approach to Penalty and Barrier functions, based on Fuzzy Logic, is proposed. Two penalty functions, that impose a progressive penalization to solutions that violate the constraints, are discussed. The implemented functions impose a low penalization when the violation of the constraints is low and a heavy penalty when the violation is high. Numerical results, obtained using twenty-eight test problems, comparing the proposed Fuzzy Logic based functions to six of the classic Penalty and Barrier functions are presented. Considering the achieved results, it can be concluded that the proposed penalty functions besides being very robust also have a very good performance.

A filter algorithm: comparison with NLP solvers

The purpose of this work is to present an algorithm to solve nonlinear constrained optimization problems, using the filter method with the inexact restoration (IR) approach. In the IR approach two independent phases are performed in each iteration—the feasibility and the optimality phases. The first one directs the iterative process into the feasible region, i.e. finds one point with less constraints violation. The optimality phase starts from this point and its goal is to optimize the objective function into the satisfied constraints space. To evaluate the solution approximations in each iteration a scheme based on the filter method is used in both phases of the algorithm. This method replaces the merit functions that are based on penalty schemes, avoiding the related difficulties such as the penalty parameter estimation and the non-differentiability of some of them. The filter method is implemented in the context of the line search globalization technique. A set of more than two hundred AMPL test problems is solved. The algorithm developed is compared with LOQO and NPSOL software packages.