1. Estimating the number of basins of attraction of multi-objective combinatorial problems
- Author
-
Madalina M. Drugan
- Subjects
Mathematical optimization ,Control and Optimization ,ComputingMethodologies_SIMULATIONANDMODELING ,Computer science ,Quadratic assignment problem ,business.industry ,Applied Mathematics ,Pareto principle ,ComputerApplications_COMPUTERSINOTHERSYSTEMS ,02 engineering and technology ,Structural basin ,Multi-objective optimization ,Attraction ,Computer Science Applications ,Local optimum ,Computational Theory and Mathematics ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Uncountable set ,Local search (optimization) ,business ,Physics::Atmospheric and Oceanic Physics - Abstract
The efficiency of local search is proportional to the number and the distribution of basins of attraction. Often combinatorial optimisation problems have a large number of local optima, uncountable with available computational resources. Approximating the number of basins of attraction and the minimal number of samples for visiting all basins at least once are complex problems for which we assume specific distributions of basins of attraction. We define two types of basins of attraction of multi-objective combinatorial optimisation problems with complementary properties. Acknowledging that each local search run generates a Pareto front of solutions, either each Pareto local solution corresponds to a basin of attraction, or a Pareto basin matches an entire Pareto local front. Simulations compare parametric and non-parametric estimators on bi-objective quadratic assignment problem instances.
- Published
- 2018