Busca avançada
Ano de início
Entree


Iterated Local Search with Perturbation based on Variables Interaction for Pseudo-Boolean Optimization

Texto completo
Autor(es):
Tinos, Renato ; Przewozniczek, Michal W. ; Whitley, Darrell ; Fieldsend, JE
Número total de Autores: 4
Tipo de documento: Artigo Científico
Fonte: PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'22); v. N/A, p. 9-pg., 2022-01-01.
Resumo

Perturbing solutions is a key factor in iterated local search (ILS). The standard approach for perturbing a solution is to randomly change a fixed number of decision variables from the current local optimum. Finding suitable values of perturbation strength is difficult. It is desirable that consecutive local optima generated by ILS be close to each other and correlated in fitness. However, if the perturbation is too small, we can get stuck in the same local optimum. We propose a new perturbation strategy for ILS applied to pseudo-Boolean optimization problems where decision variables that interact are perturbed. These interactions are identified in a variable interaction graph (VIG), that is available in gray-box optimization. For black-box optimization, we propose a local search strategy that estimates an empirical VIG. Theoretical and experimental results show that perturbation based on the VIG is efficient in random and adjacent NK landscapes. Results also show that the proposed local search strategy was able to build empirical VIGs with more than 97% of the edges of the true VIG. (AU)

Processo FAPESP: 19/07665-4 - Centro de Inteligência Artificial
Beneficiário:Fabio Gagliardi Cozman
Modalidade de apoio: Auxílio à Pesquisa - Programa eScience e Data Science - Centros de Pesquisa em Engenharia