MIDRS: A METAHEURISTIC BASED ON DETERMINISTIC FINITE AUTOMATA AND SIMULATED ANNEALING TECHNIQUE FOR BI-OBJECTIVE OPTIMIZATION COMBINATORIAL PROBLEMS

Niño Elias D., Sarabia Justo, Ardila Carlos. Nieto Wilson, Barrios Agustin. MIDRS: A Metaheuristic Based On Deterministic Finite Automata And Simulated Annealing Technique For Bi-Objective Optimization Combinatorial Problems. Proceedings of the International Conference on Computer and Computational Intelligence, ASME, ISBN: 9780791859926, Bangkok – Thailand, December 2011.

ABSTRACT

We describe a strategy for optimizing bi-objective combinatorial problems. Initially, we design and implement a metaheuristic of complexity O(n^4 ) for optimizing combinatorial problems. This metaheuristic is appointing Metaheuristic Deterministic Interchange on Automata with Simulated Annealing (MIDRS - Metaheurística de Intercambio Determinista sobre Autómatas con Recocido Simulado). MIDRS based its strategy on the theory of Deterministic Finite Automata Multi – Objective. Subsequently, we analyzed the behavior of the technique by varying the weight ratio between the objective functions. Finally, MIDRS is contrasted with high-impact global metaheuristic such as, algorithms based on Ant Colony, Evolutionary Techniques and Strategies Local Search.

http://www.asme.org/products/books/international-conference-on-computer-and-computati

A NEW METAHEURISTIC BASED ON DETERMINISTIC FINITE AUTOMATON FOR MULTI-OBJECTIVE OPTIMIZATION OF COMBINATORIAL PROBLEMS

Niño Elias D., Ardila Carlos. A New Metaheuristic Based On Deterministic Finite Automaton For Multi-Objective Optimization Of Combinatorial Problems. Proceedings of the International Conference on Computer and Computational Intelligence, ASME, ISBN: 9780791859926, Bangkok – Thailand, December 2011.

ABSTRACT

In this paper we state a novel metaheuristic based on Deterministic Finite Automaton (DFA) for the multi-objective optimization of combinatorial problems. First, we propose a new DFA based on Swapping (DFAS). DFAS allows the representation of feasible solutions space of combinatorial problems. Last, we define an algorithm that works with DFAS, it is named Exchange Deterministic Algorithm (EDA). EDA has three steps. The first step consists in create the initial solutions, the second step improves the initial solutions and the last step uses transitions between the states of the DFAS for improving the solutions. EDA was tested using well known instances of the Bi-objective Traveling Salesman Problem (TSP). EDA results were compared against Exhaustive Techniques from the specialized literature using Multiobjective Metrics. The results shows that EDA solutions are close to the Optimal Solutions.

http://www.asme.org/products/books/international-conference-on-computer-and-computati

A HYBRID IMPROVING SCHEMA BETWEEN ID3 ALGORITHMS AND NAIVE BAYES CLASSIFIERS AND ITS APPLICATION TO THE POPULATION DATABASE OF BREAST CANCER

Niño Elias D., Nieto Wilson, Riascos Carlos. A Hybrid Improving Schema Between Id3 Algorithms And Naive Bayes Classifiers And Its Application To The Population Database Of Breast Cancer. Proceedings of the International Conference on Computer and Computational Intelligence, ASME, ISBN: 9780791859926, Bangkok – Thailand, December 2011.

ABSTRACT

Analyzed the principles of the ID3 algorithm, this creates rules based on the concepts of entropy and gain with prepared data set. On the other hand, naïve Bayes classifier, allow us to classify through of the prepared data set considered probabilistic evidence. We propose a hybrid schema based on the ID3 algorithm and the naïve Bayes classifier that let us to improve the accuracy in classification tasks. We believe that this may be useful in many types of applications, so this schema serve as a support tool for research as a way to make decisions. Finally, we use experiment to prove that the hybrid schema increase the accuracy being applied to population databases of breast cancer.

http://www.asme.org/products/books/international-conference-on-computer-and-computati

IMPROVING THE CLUSTERING ALGORITHM K -MEA NS USING A NEW DISTANCE FUNCTION AND ITS APPLICATION TO THE POPULATION DATABASES OF BREAST CANCER

Niño Elias D., Nieto Wilson, Bolivar Juan. Improving The Clustering Algorithm K -Mea Ns Using A New Distance Function And Its Application To The Population Databases Of Breast Cancer, Proceedings of the International Conference on Computer and Computational Intelligence, ASME, ISBN: 9780791859926, Bangkok – Thailand, December 2011.

ABSTRACT

In this paper we propose an improvement to the clustering heuristic algorithm K-means. This improvement has been tested with databases of breast cancer. Today, clustering problems are everywhere; we can see its application in data mining, learning machines, knowledge discovery, data compression, pattern recognition, among others. One of the most popular and used clustering methods is the K -means , on this algorithm has been worked hard, basically have made several improvements, many of these base d on the definition of the initial parameters. In contrast, this paper proposes a ne w function to calculate the distance; this improvement comes from the experimental analysis of the classical algorithm. Experimentally, the improved algorithm showed a better quality solution being applied to population databases of breast cancer. Finally, we believe that this improvement may be useful in many types of applications, so this application can serve as a support tool for research on breast cancer and as a decision making in the allocation of resources for prevention and treatment.

http://www.asme.org/products/books/international-conference-on-computer-and-computati

BAYESSIAN CLASIFFIER SUPPORTED BY COVERAGE AND ACURACY IN BREAST CANCER DETECTION

Niño Elias D., Nieto Wilson, Felizzola Ricardo. Bayessian Clasiffier Supported By Coverage And Acuracy In Breast Cancer Detection.Proceedings of the International Conference on Computer and Computational Intelligence, ASME, ISBN: 9780791859926, Bangkok – Thailand, December 2011.

ABSTRACT

This article shows the importance of Bayesian classifiers for prediction in data mining, also as important components such as coverage and accuracy may improve the classification performance in themselves an analysis by performing a mathematical model such as Naive Bayes can be improved by adding coverage and precision. Finally, we believe that this improvement may be useful in many types of applications, so this application can serve as a support tool for research on breast cancer and as a decision making in the allocation of resources for prevention and treatment, also can also be used in previous applications to be improved in many ways.

http://www.asme.org/products/books/international-conference-on-computer-and-computati

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.