Evolution algorithms in combinatorial optimization

doi:10.1016/0167-8191(88)90098-1

Parallel Computing

Volume 7, Issue 1, April 1988, Pages 65-85

https://doi.org/10.1016/0167-8191(88)90098-1 Get rights and content

Abstract

Evolution algorithms for combinatorial optimization have been proposed in the 70's. They did not have a major influence. With the availability of parallel computers, these algorithms will become more important.

In this paper we discuss the dynamics of three different classes of evolution algorithms: network algorithms derived from the replicator equation, Darwinian algorithms and genetic algorithms inheriting genetic information.

We present a new genetic algorithm which relies on intelligent evolution of individuals. With this algorithm, we have computed the best solution of a famous travelling salesman problem. The algorithm is inherently parallel and shows a superlinear speedup in multiprocessor systems.

References (30)

C.E. Houstis et al.
Partitioning PDE computations: Methods and performance evaluation
Parallel Comput.
(1987)
H. Mühlenbein et al.
New solutions to the mapping problem of parallel systems — The evolution approach
Parallel Comput.
(1987)
M.J. Berger et al.
A partitioning strategy for nonuniform problems on multiprocessors
IEEE Trans. Comput.
(1987)
T. Bosenick et al.
Boltzmann and Darwinin strategies in complex optimization
Phys. Lett.
(1987)
R.M. Brady
Optimization strategies gleaned from biological evolution
Nature
(1985)
W. Ebeling et al.
Models of evolution systems and their application to optimization problems
System Anal. Model. Simul.
(1986)
W. Ebeling et al.
Physik der Selbstorganisation und Evolution
(1980)
G.C. Fox
A review of automatic load balancing and decomposition methods for the hypercube
Caltech Report C³P385
(1986)
G.C. Fox et al.
Load balancing by a neural network
Caltech Report C³P363
(1986)
M. Gorges-Schleuter and H. Mühlenbein, The traveling salesman problem — An evolution approach, to be...

J. Hofbauer et al.

Evolutionstheorie und dynamische Systeme, Mathematische Aspekte der Selektion

(1984)

J.H. Holland

Adaptation in Natural and Artificial Systems

(1975)

J.J. Hopfield et al.

“Neural” Computation of decisions in optimization problems

Biol. Cybern.

(1985)

A. Iwainsky et al.

Network decomposition for the optimization of connected structures

Networks

(1986)

B.W. Kernighan et al.

An efficient heuristic procedure for partitioning graphs

Bell System Tech. J.

(February 1970)

Cited by (286)

Simulation–optimization configurations for real-time decision-making in fugitive interception
2024, Simulation Modelling Practice and Theory
Simulation–optimization models are well-suited for real-time decision-support to the control room for search and interception of fugitives by Police on a road network, due to their ability to encode complex behavior while still optimizing the interception.
The typical simulation–optimization configuration is simulation model optimization, where the simulation model describes the system to be optimized, and the optimizer attempts to find the combination of decision variables that maximizes the interception probability. However, the repeated evaluation of the simulation model leads to high computation time, thus rendering it inadequate for time-constrained decision contexts. To support police interception operations in real-time, timely calculation of the solution is essential. Sequential simulation–optimization, where the simulation model, with its rich behavior, constructs (part of) the constraints of an optimization problem, could decrease the computation time.
We compare the computation time for two configurations of simulation–optimization (typical simulation model optimization and sequential simulation–optimization) for various problem instances of the fugitive interception problem. We show that sequential simulation–optimization reduces the computation time of large instances of the fugitive interception case study ten-fold. This result illustrates the potential of sequential simulation–optimization to mitigate the expensive optimization of simulation models.
Termite life cycle optimizer
2023, Expert Systems with Applications
This paper introduces a novel bio-inspired meta-heuristic optimization algorithm, named termite life cycle optimizer (TLCO), which is based on both the life cycle of a termite colony and the modulation of movement strategies used by many animal species in nature. Termite colonies are comprised of three distinct castes: the workers, the soldiers and the reproductive termites. Each caste undertakes a set of specific tasks that ensure the growth and survival of the colony. TLCO mimics the activities of these three castes that are implemented in a mathematical model. The model is then used to find the global optimum in classic optimization problems. First, the behaviors of the workers, soldiers and reproductive termites are used to simulate a balance between the tasks of exploration and exploitation. Second, the initial population securely records the information obtained at each iteration and transmits it to workers and soldiers at the next iteration. This process is repeated until the global optimum is found with the smallest error. Besides, a new proposed function combined with Lévy flight is used to modulate the movement of termites that increases its flexibility. Thus, TLCO can cover both long distances during the first iterations to improve the convergence rate and shorter distances during the last iterations to enhance the level of accuracy. We then compare the performances of TLCO with other well-known nature-inspired algorithms using 23 classical benchmark functions, CEC2005 benchmark functions, and five real engineering design problems. The results demonstrate the effectiveness and reliability of TLCO in solving these optimization problems. Source codes of TLCO is publicly available at http://goldensolutionrs.com/termite-life-cycle-optimizer.html.
Golden jackal optimization: A novel nature-inspired optimizer for engineering applications
2022, Expert Systems with Applications
A new nature-inspired optimization method, named the Golden Jackal Optimization (GJO) algorithm is proposed, which aims to provide an alternative optimization method for solving real-world engineering problems. GJO is inspired by the collaborative hunting behaviour of the golden jackals (Canis aureus). The three elementary steps of algorithm are prey searching, enclosing, and pouncing, which are mathematically modelled and applied. The ability of proposed algorithm is assessed, by comparing with different state of the art metaheuristics, on benchmark functions. The proposed algorithm is further tested for solving seven different engineering design problems and introduces a real implementation of the proposed method in the field of electrical engineering. The results of the classical engineering design problems and real implementation verify that the proposed algorithm is appropriate for tackling challenging problems with unidentified search spaces.
A GA-based algorithm meets the fair ranking problem
2021, Information Processing and Management
Ranking items is a vital component in almost every application dealing with selecting the most suitable items among a pool of candidates. Yet, specific individuals or groups may be systematically disadvantaged in getting the opportunity of appearing on the ranking list. The fair ranking problem aims at mitigating the bias imposed on protected groups (i.e., disadvantaged groups) while preserving the total quality of the ranking list as high as possible. FA*IR is one of the existing algorithms, which finds the exact solutions for only one protected group, considering a given minimum number of protected items at every prefix of a ranking list. However, when an item belongs to more than two protected groups achieving optimal solutions gets more difficult. This paper proposes an algorithm called FARGO, a fair ranking algorithm based on the genetic algorithm (GA) enhanced by the simulated annealing (SA) that is able to handle any number of protected groups. A new objective function is also proposed by incorporating the main goals of the problem, which is utilized as FARGO's fitness function. Furthermore, a novel evaluation metric named Expected Gain Ratio (EGR) is introduced to assess a fair ranking algorithm's output. Experimental results on real-world datasets demonstrate that FARGO attains comparative performance with FA*IR for one protected group and finds near-optimal solutions for more than one protected group in terms of NDCG and EGR. Note that involving other concepts such as exposure is not a matter of this paper and can be an interesting subject for further studies.
Fractional-Order Water Flow Optimizer
2024, International Journal of Computational Intelligence Systems
Automated Data-Driven Discovery of Material Models Based on Symbolic Regression: A Case Study on Human Brain Cortex
2024, SSRN

View all citing articles on Scopus

View full text

Evolution algorithms in combinatorial optimization

Abstract

Parallel Comput.

Parallel Comput.

A partitioning strategy for nonuniform problems on multiprocessors

IEEE Trans. Comput.

Boltzmann and Darwinin strategies in complex optimization

Phys. Lett.

Optimization strategies gleaned from biological evolution

Nature

Models of evolution systems and their application to optimization problems

System Anal. Model. Simul.

Physik der Selbstorganisation und Evolution

A review of automatic load balancing and decomposition methods for the hypercube

Caltech Report C3P385

Load balancing by a neural network

Caltech Report C3P363