An Evolutionary Strategy based on Partial Imitation for Solving Optimization Problems
In this work we introduce an evolutionary strategy to solve combinatorial
optimization tasks, i.e. problems characterized by a discrete search space. In
particular, we focus on the Traveling Salesman Problem (TSP), i.e. a famous
problem whose search space grows exponentially, increasing the number of
cities, up to becoming NP-hard. The solutions of the TSP can be codified by
arrays of cities, and can be evaluated by fitness, computed according to a cost
function (e.g. the length of a path). Our method is based on the evolution of
an agent population by means of an imitative mechanism, we define partial
imitation'. In particular, agents receive a random solution and then,
interacting among themselves, may imitate the solutions of agents with a higher
fitness. Since the imitation mechanism is only partial, agents copy only one
entry (randomly chosen) of another array (i.e. solution). In doing so, the
population converges towards a shared solution, behaving like a spin system
undergoing a cooling process, i.e. driven towards an ordered phase. We
highlight that the adopted partial imitation' mechanism allows the population
to generate solutions over time, before reaching the final equilibrium. Results
of numerical simulations show that our method is able to find, in a finite
time, both optimal and suboptimal solutions, depending on the size of the
considered search space.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
A New Distributed Evolutionary Computation Technique for Multi-Objective Optimization
Now-a-days, it is important to find out solutions of Multi-Objective Optimization Problems (MOPs). Evolutionary Strategy helps to solve such real world problems efficiently and quickly. But sequential Evolutionary Algori…
Evolutionary AlgorithmsEvolutionary Preference Sampling for Pareto Set Learning
Recently, Pareto Set Learning (PSL) has been proposed for learning the entire Pareto set using a neural network. PSL employs preference vectors to scalarize multiple objectives, facilitating the learning of mappings from…
Evolutionary AlgorithmsCooperative guidance of multiple missiles: a hybrid co-evolutionary approach
Cooperative guidance of multiple missiles is a challenging task with rigorous constraints of time and space consensus, especially when attacking dynamic targets. In this paper, the cooperative guidance task is described …
continuous-controlContinuous ControlA Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving
Large language models (LLMs) are increasingly integrated with evolutionary computation to support optimization tasks. This survey primarily focuses on evolutionary optimization, i.e., optimization based on evolutionary c…
Detect and Act: Automated Dynamic Optimizer through Meta-Black-Box Optimization
Dynamic Optimization Problems (DOPs) are challenging to address due to their complex nature, i.e., dynamic environment variation. Evolutionary Computation methods are generally advantaged in solving DOPs since they resem…
Reinforcement Learning