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
• City of the host institution: Ribeirão Preto
• 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)

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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)

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)

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)

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)