CHAPTER BOOK: Evolutionary Algorithms based on te Automata Theory for the Multiobjective Optimization of Combinatorial Problems

Hi everyone:

This is my first chapter book, here is the information of the book:

Genetic Algorithm / Book 2 ISBN 979-953-307-879-2 The book covers the next topics:

* Evolutionary algorithms
* Evolutionary computing
* Metaheuristics
* Stochastic optimization
* Optimization
* Genetic representation
* Population growth estimation
* Web intelligence domains
* Pattern recognition
* Data mining
* Soft computing
* Bioinformatics
* Learning systems

It will be avaliable by January 2012. In this chapter I review all the techniques proposed by me and a novel metaheuristic is designed. Also, the tested are considered very hard, I work with instance from Bi to Quint-objectives. Here is a brief description of the chapter content:

1. Introduction. (Research regarding to Combinatorial Optimization)

2. Preliminares.
2.1. Multiobjective Optimization
2.2. Genetic Algorithms
2.3. Simulated Annealing Algorithms
2.4. Metaheuristic of Deterministic Swapping (MODS).

3. Simulated Annealing Metaheuristic of Deterministic Swapping (SAMODS)

4. Evolutionary Metaheuristic of Deterministic Swapping (EMODS)

5. Genetic Simulated Annealing Metaheuristic of Deterministic Swapping (SAGAMODS)

6. Experimental Analysis
6.1. Experimental Settings.
6.2. Performance Metrics (Generations of No Dominated Vector (GNDV), Spacing (S), Generational Distance (GD), Inverse Generational Distance (IGD)...)
6.3. Experimental Results
6.4. Analysis

7. Conclusions.

8. References.

A graphical comparison of the results for three objective instances is shown in the next figure:

SAMODS & SAGAMODS: Novel Algorithms based on the Automata Theory for the Multiobjective Optimization of Combinatorial Problems

This paper was accepted for publication in The International Journal of Artificial Intelligence. Special Issue in Metaheuristic in Artificial Intelligence. It will be available by January of 2012.

Authors: Elias D. Nino

Here is the abstract:

This paper states two novel algorithms based on the Automata Theory for the Multiobjective Optimization of Combinatorial Problems. The first algorithm proposed is named SAMODS. It is a hybrid Simulated Annealing MODS inspired algorithm. The main idea behind this approach consists in optimizing a Combinatorial Problem changing the Angle Improvement; this is a novel theory maintain in the classic weighted sum metric. SAMODS avoids unfeasible solutions fall back on the MODS theory. Also, it avoids local optimum due to the use of Boltzmann Distribution Probability for accepting bad solutions as good solutions. The last proposed algorithm was named SAGAMODS. It is an Evolutionary Algorithm based on the MODS theory. In addition to the advantages of SAMODS, SAGAMODS avoids in two times local optimums because of its Crossover Step. It is taken from the Natural Selection Theory that allows creating new solutions (next generation) support in the current solutions (actual generation). Only the best solutions survive. The proposed algorithms were tested using instances from the well-known TSPLIB. The test was made using problems with two objectives, three objectives, four objectives and five objectives inclusive. The proposed algorithms were compared using metrics from the specialized literature of the Multiobjective Optimization. The results of the metrics applied to the algorithms shows that MODS algorithm was superseded up to 100% out of 100%, in some of the instances worked, by the proposed algorithms.

Graphic Comparison MODS, SAMODS and SAGAMODS for Three-objectives instances of TSP:

For a detail definition and analysis of the results, wait for the entire paper.

MODS: A Novel Metaheuristic of Deterministic Swapping for the Multi – Objective Optimization of Combinatorials Problems

Tipo de Publicación: Articulo
Categoria: C (COLCIENCIAS)
Idioma: Inglés
Revista: Elias D. Niño, Carlos J. Ardila , Agustín Barrios and Yezid Donoso. MODS: A Novel Metaheuristic of Deterministic Swapping for the Multi – Objective Optimization of Combinatorials Problems. Computer Technology and Application. Volume 2, Number 4, 2011

Abstract

This paper states a new metaheuristic based on Deterministic Finite Automata (DFA) for the multi – objective optimization of combinatorial problems. First, a new DFA named Multi – Objective Deterministic Finite Automata (MDFA) is defined. MDFA allows the representation of the feasible solutions space of combinatorial problems. Second, it is defined and implemented a metaheuritic based on MDFA theory. It is named Metaheuristic Of Deterministic Swapping (MODS). MODS is a local search strategy that works using a MDFA. Due to this, MODS never take into account unfeasible solutions. Hence, it is not necessary to verify the problem constraints for a new solution found. Lastly, MODS is tested using well know instances of the Bi – Objective Traveling Salesman Problem (TSP) from TSPLIB. Its results were compared with eight Ant Colony inspired algorithms and two Genetic algorithms taken from the specialized literature. The comparison was made using metrics such as Spacing, Generational Distance, Inverse Generational Distance and No-Dominated Generation Vectors. In every case, the MODS results on the metrics were always better and in some of those cases, the superiority was 100%.

A novel Algorithm based on Deterministic Finite Automaton for solving the mono-objective Symmetric Traveling Salesman Problem

Tipo de Publicación: Articulo
Categoria: SCOPUS
Idioma: Inglés
Revista: Elias Niño, Carlos Ardila, Daladier Jabba, Yezid Donoso. A novel Algorithm based on Deterministic Finite Automaton for solving the mono-objective Symmetric Traveling Salesman Problem. International Journal of Artificial Intelligence, Volume 5, Number A10. ISSN 0974-0635. 2010.

Abstract

This paper states an Algorithm Based on Finite Automata: the Exchange Deterministic Algorithm (EDA). EDA is an improvement of the EDNR algorithm(Ausiello, Feuerstein, Leonardi, Stougie and Talamo, 2001). that is applied to one of the classic problems in combinatorial optimization: The Symmetric Traveling Salesman Problem (TSP). First, the feasible solutions space of TSP was modeled by using a Deterministic Finite Automaton of Swapping (DFAS). DFAS is a data structure that allows the representation of the feasible solutions space of a combinatorial problem. Once that structure is defined, the algorithm is applied to different random scenarios of the TSP in order to contrast proximity with the global optimum obtained by exhaustive searching. Afterwards, the algorithm is applied to a particular problem, and the results are compared with others that were obtained by techniques such as Ant Colony, GRASP, Genetic Algorithms, Simulated Annealing, and Tabu Search(Bin and Raidl, 2008). EDA surpassed the others in terms of number of iterations the optimum is obtained.

DESCARGAR AQUI/DOWNLOAD HERE

A Genetic Algorithm for Multiobjective Hard Scheduling Optimization

Tipo de Publicación: Articulo
Categoria: ISI Web of Knowledge
Idioma: Inglés
Revista: International Journal of Computers, Communications & Control (IJCCC) No.25 (jun. 2009) ISSN 1841 - 9836; E-ISSN 1841 - 9844 - Agora University Editing House - CCC Publications - Oradea - Rumania. Mayo 2010.

Resumen

This paper proposes a genetic algorithm for multiobjective scheduling optimization based in the object oriented design with constrains on delivery times, process precedence and resource availability.

Initially, the programming algorithm (PA) was designed and implemented, taking into account all constraints mentioned. This algorithm’s main objective is, given a sequence of production orders, products and processes, calculate its total programming cost and time.

Once the programming algorithm was defined, the genetic algorithm (GA) was developed for minimizing two objectives: delivery times and total programming cost. The stages defined for this algorithm were: selection, crossover and mutation. During the first stage, the individuals composing the next generation are selected using a strong dominance test. Given the strong restrictions on the model, the crossover stage utilizes a process level structure (PLS) where processes are grouped by its levels in the product tree. Finally during the mutation stage, the solutions are modified in two different ways (selected in a random fashion): changing the selection of the resources of one process and organizing the processes by its execution time by level.

In order to obtain more variability in the found solutions, the production orders and the products are organized with activity planning rules such as EDD, SPT and LPT. For each level of processes, the processes are organized by its processing time from lower to higher (PLU), from higher to lower (PUL), randomly (PR), and by local search (LS). As strategies for local search, three algorithms were implemented: Tabu Search (TS), Simulated Annealing (SA) and Exchange Deterministic Algorithm (EDA). The purpose of the local search is to organize the processes in such a way that minimizes the total execution time of the level.

Finally, Pareto fronts are used to show the obtained results of applying each of the specified strategies. Results are analyzed and compared.

Keywords: Scheduling, Process, Genetic Algorithm, Local search, Pareto Front.

DESCARGAR AQUI/DOWNLOAD HERE