Recombination by decomposition in evolutionary computation

• Grant number: 15/06462-1
• Support Opportunities: Regular Research Grants
• Start date: July 01, 2015
• End date: June 30, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Renato Tinós
• Grantee: Renato Tinós
• Host Institution: Faculdade de Filosofia, Ciências e Letras de Ribeirão Preto (FFCLRP). Universidade de São Paulo (USP). Ribeirão Preto , SP, Brazil
• Associated researchers: Evandro Eduardo Seron Ruiz ; Zhao Liang

Abstract

The recombination of solutions is important for evolutionary computation, particularly for genetic algorithms. Recombination is also interesting in other optimization strategies: it can be used to recombine solutions produced in different runs of an algorithm or to recombine solutions produced by different algorithms. The main objective of this project is the investigation of new operators for recombination by decomposition in problems where the evaluation function is composed by a sum of terms. Recombination by decomposition partitions the decision variables of the problem in order to allow the decomposition of the evaluation function. In this way, it allows to find, with computational cost proportional to the cost of evaluating one solution of the problem, the best solution among a number of offspring solutions that grows exponentially with the number of partitions found by the recombination operator. In this project, recombination by decomposition operators will be investigated in combinatorial optimization problems involving graphs and in k-bounded pseudo-Boolean optimization problems. (AU)

Scientific publications

(8)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

TINOS, RENATO; ZHAO, LIANG; CHICANO, FRANCISCO; WHITLEY, DARRELL. NK Hybrid Genetic Algorithm for Clustering. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, v. 22, n. 5, p. 748-761, OCT 2018. (13/07375-0, 15/50122-0, 15/06462-1)

SANCHES, DANILO; WHITLEY, DARRELL; TINOS, RENATO; ACM. Improving an Exact Solver for the Traveling Salesman Problem using Partition Crossover. PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), v. N/A, p. 8-pg., 2017-01-01. (15/06462-1)

SANCHES, DANILO; WHITLEY, DARRELL; TINOS, RENATO; ACM. Building a Better Heuristic for the Traveling Salesman Problem: Combining Edge Assembly Crossover and Partition Crossover. PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), v. N/A, p. 8-pg., 2017-01-01. (15/06462-1)

TINOS, RENATO; WHITLEY, DARRELL; OCHOA, GABRIELA. A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling between Local Optima. EVOLUTIONARY COMPUTATION, v. 28, n. 2, p. 255-288, JUN 2020. (16/18615-0, 15/06462-1, 13/07375-0)

CHICANO, FRANCISCO; OCHOA, GABRIELA; WHITLEY, DARRELL; TINOS, RENATO; AGUIRRE, H. Enhancing Partition Crossover with Articulation Points Analysis. GECCO'18: PROCEEDINGS OF THE 2018 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, v. N/A, p. 8-pg., 2018-01-01. (15/06462-1)

TINOS, RENATO; WHITLEY, DARRELL; IEEE. A Fusion Mechanism for the Generalized Asymmetric Partition Crossover. 2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2018-01-01. (15/06462-1)

CHICANO, FRANCISCO; WHITLEY, DARRELL; OCHOA, GABRIELA; TINOS, RENATO; ACM. Optimizing One Million Variable NK Landscapes by Hybridizing Deterministic Recombination and Local Search. PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), v. N/A, p. 8-pg., 2017-01-01. (15/06462-1)

TINOS, RENATO; YANG, SHENGXIANG. A framework for inducing artificial changes in optimization problems. INFORMATION SCIENCES, v. 485, p. 486-504, JUN 2019. (16/18615-0, 15/06462-1, 13/07375-0)