Artificial Intelligence & Multi Criteria Decision Making
Introduction
Artificial intelligence is not just machine learning, but also encompasses a family of problem solving algorithms. These algorithms, that may be futher differentiated into Constraint Satisfaction and Search, may be used for optimisation problems subject to a set of constraints or objectives.
The following approaches may be integrated into a decision support system to support operators in situations such as the mission planning problem.
Constraint Satisfaction Programming (CSP)
- Constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy.
- Constraint programming is the use of constraints as a programming language to encode and solve problems.
- CSP provides a methodology to mathematically represent a problem in form of a set of constraints
- These methods allows to search for a feasible solution, or for an optimal solution
- Most of the methods are NP hard.
- For example, [1]
Toolkits & Solvers
- Minizinc: MiniZinc is a free and open-source constraint modeling language
- Choco
- CPLEX CP Optimizer [IBM]
- ECLiPSe
- Gecode
- Google OR-Tools
- Opturion CPX
- OscaR
XCSP3 Competition: Constraint Satisfaction Problem & Constrained Optimization Problem.
Evolutionary Computing (EC)
- Evolutionary Computation is a family of algorithms for global optimisation inspired by biological evolution.
- In evolutionary computation, an initial set of candidate solutions is generated and iteratively updated.
- Each new generation is produced by stochastically removing less desired solutions, and introducing small random changes.
- Basic operations & concepts: mutation, crossover (reproduction), fitness function, selection, offspring…
Classes of evolutionary algorithms:
- Genetic Algorithms (GA)
- Genetic Programming (GP)
- Evolutionary Strategy (ES)
- Evolutionary Programming (EP)
- Learning Classifier System (LCS)
Evolutionary Multi-Objective Optimisation (EMOO) & Multi-objective evolutionary algorithms (MOEAs)
Multi-objective optimisation (also known as multi-objective programming, vector optimisation, multicriteria optimisation, multiattribute optimisation or Pareto optimisation) is an area of multiple criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. It usually involves an arbitrary optimisation problem with k objectives, which are all to be maximised/minimised and all equally important.
For a nontrivial multi-objective optimization problem, no single solution exists that simultaneously optimises each objective. In that case, the objective functions are said to be conflicting, and there exists a (possibly infinite) number of Pareto optimal solutions. A solution is called non-dominated, Pareto optimal, Pareto efficient or non-inferior, if none of the objective functions can be improved in value without degrading some of the other objective values.
These techniques are applied when multiple, often conflicting, objectives arise (e.g. max. inter-distance, min. intra-distance).
Evolutionary Multi-Objective Optimization (EMOO) is a subdiscipline combining the fields of evolutionary computation and classical multiple criteria decision making [2].
Key concepts:
- Dominance
- Pareto dominance
- Pareto set and front
- Pareto optimality
- Crowding distance
- Hypervolume
Toolkits & Solvers
Tools & Frameworks (EC & MOEAs):
- NSGA/NSGA-II (Non dominated Sorting Genetic Algorithm) [3]
- SPEA/SPEA2 (Strength Pareto Evolutionary Algorithm)
- MOEA/D
- VEGA (Vector Evaluated Genetic Algorithms)
- MOGA (Multi-objective GA) , NPGA (Niched-Pareto Genetic Algorithm)
- PPES (Predator-Prey Evolution Strategy)
- PGEN (Pareto surface generation for convex multi-objective instances)
- SMS-EMOA (S-metric selection evolutionary multi-objective algorithm)
- Multi-objective particle swarm optimisation
- ε-MOEA, GDE3, PAES, PESA2, SPEA2, IBEA, SMS-EMOA, SMPSO, OMOPSO, CMA-ES
For an overview of evolutionary optimisation techniques, see [4].
References
[1]: Nogareda A.M., Del Ser J., Osaba E., Camacho D. (2020). On the Design of Hybrid Bio-inspired Meta-heuristics for Complex Multi-Attribute Vehicle Routing Problems, Expert Systems
[2]: Fonseca, C. M., Fleming, P. J. (1993). Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Icga Vol. 93, No. July, pp. 416-423
[3]: Deb K., et al. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6(2), pp. 182-197
[4]: Del Ser J., Camacho D., et al. (2019). Bio-inspired computation: Where we stand and what’s next, Swarm and Evolutionary Computation, Vol. 48, pp. 220-250
Bibliography
Alpaydin, E. (2009). Introduction to machine learning. MIT press.
Del Ser, J., Osaba, E., Molina, D., Yang, X. S., Salcedo-Sanz, S., Camacho, D., … & Herrera, F. (2019). Bio-inspired computation: Where we stand and what’s next. Swarm and Evolutionary Computation, 48, 220-250.
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000, September). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In International conference on parallel problem solving from nature (pp. 849-858). Springer, Berlin, Heidelberg.
Eiben, A. E., & Smith, J. E. (2003). Introduction to evolutionary computing (Vol. 53, p. 18). Berlin: springer.
Marriott, K., Stuckey, P. J., & Stuckey, P. J. (1998). Programming with constraints: an introduction. MIT press.
Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6), 712-731.