Editing Fitness function (section)

== Multi-objective optimization ==
Practical applications usually aim at optimizing multiple and at least partially conflicting objectives. Two fundamentally different approaches are often used for this purpose, [[Multi-objective optimization|Pareto optimization]] and optimization based on fitness calculated using the [[Weight function|weighted sum]].<ref name=":0">{{Cite book |last=Miettinen |first=Kaisa |url=https://www.researchgate.net/publication/242505658 |title=Multiobjective Optimization: Interactive and Evolutionary Approaches |date=2008 |publisher=Springer |isbn=978-3-540-88907-6 |editor-last=Branke |editor-first=Jürgen |series=Lecture Notes in Computer Science |volume=5252 |location=Berlin, Heidelberg |pages=1–26 |language=en |chapter=Introduction to Multiobjective Optimization: Noninteractive Approaches |doi=10.1007/978-3-540-88908-3 |editor-last2=Deb |editor-first2=Kalyanmoy |editor-last3=Miettinen |editor-first3=Kaisa |editor-last4=Słowiński |editor-first4=Roman |s2cid=15375227}}</ref>

=== Weighted sum and penalty functions ===
When optimizing with the weighted sum, the single values of the <math>O</math> objectives are first normalized so that they can be compared. This can be done with the help of costs or by specifying target values and determining the current value as the degree of fulfillment. Costs or degrees of fulfillment can then be compared with each other and, if required, can also be mapped to a uniform fitness scale. [[Without loss of generality]], fitness is assumed to represent a value to be maximized. Each objective <math>o_i</math> is assigned a weight <math>w_i</math> in the form of a percentage value so that the overall raw fitness <math>f_{raw}</math> can be calculated as a weighted sum: <blockquote><math>f_{raw} = \sum_{i=1}^O{o_i \cdot w_i} \quad \mathsf{with} \quad \sum_{i=1}^O{w_i} = 1 </math> </blockquote>A violation of <math>R</math> restrictions <math>r_j</math> can be included in the fitness determined in this way in the form of [[Penalty method|penalty functions]]. For this purpose, a function <math>pf_j(r_j)</math> can be defined for each restriction which returns a value between <math>0</math> and <math>1</math> depending on the degree of violation, with the result being <math>1</math> if there is no violation. The previously determined raw fitness is multiplied by the penalty function(s) and the result is then the final fitness <math>f_{final}</math>:<ref name=":1" /> <blockquote><math>f_{final}= f_{raw} \cdot \prod_{j=1}^R{pf_j(r_j)} = \sum_{i=1}^O{(o_i \cdot w_i)} \cdot \prod_{j=1}^R{pf_j(r_j)}</math> </blockquote>This approach is simple and has the advantage of being able to combine any number of objectives and restrictions. The disadvantage is that different objectives can compensate each other and that the weights have to be defined before the optimization. This means that the compromise lines must be defined before optimization, which is why optimization with the weighted sum is also referred to as the [[Multi-objective optimization#A priori methods|a priori method]].<ref name=":0" /> In addition, certain solutions may not be obtained, see the section on the ''[[Fitness function#Comparison of both types of assessment|comparison of both types of optimization]]''.

=== Pareto optimization ===
A solution is called Pareto-optimal if the improvement of one objective is only possible with a deterioration of at least one other objective. The set of all Pareto-optimal solutions, also called Pareto set, represents the set of all optimal compromises between the objectives. The figure below on the right shows an example of the Pareto set of two objectives <math>f_1</math> and <math>f_2</math> to be maximized. The elements of the set form the Pareto front (green line). From this set, a human decision maker must subsequently select the desired compromise solution.<ref name=":0" /> Constraints are included in Pareto optimization in that solutions without constraint violations are per se better than those with violations. If two solutions to be compared each have constraint violations, the respective extent of the violations decides.<ref name=":2">{{Cite book |last=Deb |first=Kalyanmoy |url=https://www.researchgate.net/publication/242505658 |title=Multiobjective Optimization: Interactive and Evolutionary Approaches |date=2008 |publisher=Springer |isbn=978-3-540-88907-6 |editor-last=Branke |editor-first=Jürgen |series=Lecture Notes in Computer Science |volume=5252 |location=Berlin, Heidelberg |pages=58–96 |language=en |chapter=Introduction to Evolutionary Multiobjective Optimization |doi=10.1007/978-3-540-88908-3 |editor-last2=Deb |editor-first2=Kalyanmoy |editor-last3=Miettinen |editor-first3=Kaisa |editor-last4=Słowiński |editor-first4=Roman |s2cid=15375227}}</ref>

It was recognized early on that EAs with their simultaneously considered solution set are well suited to finding solutions in one run that cover the Pareto front sufficiently well.<ref name=":2" /><ref>{{Cite journal |last1=Fonseca |first1=Carlos M. |last2=Fleming |first2=Peter J. |date=1995 |title=An Overview of Evolutionary Algorithms in Multiobjective Optimization |url=https://direct.mit.edu/evco/article/3/1/1-16/733 |journal=Evolutionary Computation |language=en |volume=3 |issue=1 |pages=1–16 |doi=10.1162/evco.1995.3.1.1 |s2cid=8530790 |issn=1063-6560|url-access=subscription }}</ref> They are therefore well suited as [[Multi-objective optimization#A posteriori methods|a-posteriori methods]] for multi-objective optimization, in which the final decision is made by a human decision maker after optimization and determination of the Pareto front.<ref name=":0" /> Besides the SPEA2,<ref>{{Cite journal |last1=Eckart |first1=Zitzler |last2=Marco |first2=Laumanns |last3=Lothar |first3=Thiele |date=2001 |title=SPEA2: Improving the strength pareto evolutionary algorithm |url= |journal=Technical Report, Nr. 103. Computer Engineering and Networks Laboratory (TIK) |language=en |publisher=ETH Zürich 2001 |pages= |doi=10.3929/ethz-a-004284029|s2cid=16584254 }}</ref> the NSGA-II<ref>{{Cite journal |last1=Deb |first1=K. |last2=Pratap |first2=A. |last3=Agarwal |first3=S. |last4=Meyarivan |first4=T. |date=2002 |title=A fast and elitist multiobjective genetic algorithm: NSGA-II |url=https://ieeexplore.ieee.org/document/996017 |journal=IEEE Transactions on Evolutionary Computation |volume=6 |issue=2 |pages=182–197 |doi=10.1109/4235.996017|s2cid=9914171 }}</ref> and NSGA-III<ref>{{Cite journal |last1=Deb |first1=Kalyanmoy |last2=Jain |first2=Himanshu |date=2014 |title=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints |url=https://ieeexplore.ieee.org/document/6600851 |journal=IEEE Transactions on Evolutionary Computation |volume=18 |issue=4 |pages=577–601 |doi=10.1109/TEVC.2013.2281535 |s2cid=206682597 |issn=1089-778X|url-access=subscription }}</ref><ref>{{Cite journal |last1=Jain |first1=Himanshu |last2=Deb |first2=Kalyanmoy |date=2014 |title=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach |url=https://ieeexplore.ieee.org/document/6595567 |journal=IEEE Transactions on Evolutionary Computation |volume=18 |issue=4 |pages=602–622 |doi=10.1109/TEVC.2013.2281534 |s2cid=16426862 |issn=1089-778X|url-access=subscription }}</ref> have established themselves as standard methods.

The advantage of Pareto optimization is that, in contrast to the weighted sum, it provides all alternatives that are equivalent in terms of the objectives as an overall solution. The disadvantage is that a visualization of the alternatives becomes problematic or even impossible from four objectives on. Furthermore, the effort increases exponentially with the number of objectives.<ref name=":1">{{Cite journal |last1=Jakob |first1=Wilfried |last2=Blume |first2=Christian |date=2014-03-21 |title=Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts |journal=Algorithms |language=en |volume=7 |issue=1 |pages=166–185 |arxiv=2203.02697 |doi=10.3390/a7010166 |issn=1999-4893|doi-access=free }}</ref> If there are more than three or four objectives, some have to be combined using the weighted sum or other aggregation methods.<ref name=":0" />

=== Comparison of both types of assessment ===
[[File:ParetoFront und Gewichtete Summe.png|left|thumb|Relationship between the Pareto front and the weighted sum. The set of feasible solutions <math>Z</math> is partially bounded by the Pareto front (green).<ref name=":1" />]]
[[File:ParetoFront nicht konvex.png|thumb|Example of a non-convex Pareto front<ref name=":1" />]]
With the help of the weighted sum, the total Pareto front can be obtained by a suitable choice of weights, provided that it is [[Convex set|convex]].<ref>{{Cite book |last=Miettinen |first=Kaisa |url=http://link.springer.com/10.1007/978-1-4615-5563-6 |title=Nonlinear Multiobjective Optimization |date=1998 |publisher=Springer US |isbn=978-1-4613-7544-9 |series=International Series in Operations Research & Management Science |volume=12 |location=Boston, MA |doi=10.1007/978-1-4615-5563-6}}</ref> This is illustrated by the adjacent picture on the left. The point <math>\mathsf{P}</math> on the green Pareto front is reached by the weights <math>w_1</math> and <math>w_2</math>, provided that the EA converges to the optimum. The direction with the largest fitness gain in the solution set <math>Z</math> is shown by the drawn arrows.

In case of a non-convex front, however, non-convex front sections are not reachable by the weighted sum. In the adjacent image on the right, this is the section between points <math>\mathsf{A}</math> and <math>\mathsf{B}</math>. This can be remedied to a limited extent by using an extension of the weighted sum, the ''cascaded weighted sum''.<ref name=":1" />

Comparing both assessment approaches, the use of Pareto optimization is certainly advantageous when little is known about the possible solutions of a task and when the number of optimization objectives can be narrowed down to three, at most four. However, in the case of repeated optimization of variations of one and the same task, the desired lines of compromise are usually known and the effort to determine the entire Pareto front is no longer justified. This is also true when no human decision is desired or possible after optimization, such as in automated decision processes.<ref name=":1" />