moptipy.algorithms.so.fitnesses package¶
Fitness assignment processes.
Fitness assignment processes are modules of the fully-configurable Evolutionary Algorithm Direct fitness assignment uses the objective values directly as fitness. Together with fitness proportionate selection ( John Henry Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, MI, USA: University of Michigan Press. 1975. ISBN: 0-472-08460-7 David Edward Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. 1989. ISBN: 0-201-15767-5 Bases: Objective values are used as fitness directly. This is the most primitive and basic fitness assignment strategy. It does not give preference to new solutions over old solutions if both have the same objective value. In this, it is different from The Frequency Fitness Assignment (FFA) Process. Frequency Fitness Assignment (FFA) replaces all objective values with their encounter frequencies in the selection decisions. The more often an objective value is encountered, the higher gets its encounter frequency. Therefore, local optima are slowly receiving worse and worse fitness. Notice that this implementation of FFA has a slight twist to it: It will incorporate the iteration index ( This can make the EA with FFA compatible with the Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value. IEEE Transactions on Evolutionary Computation 25(2):307-319. April 2021. Preprint available at arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. https://dx.doi.org/10.1109/TEVC.2020.3032090 Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient. IEEE Transactions on Evolutionary Computation (TEVC). 2022. Early Access. https://dx.doi.org/10.1109/TEVC.2022.3191698 Thomas Weise, Mingxu Wan, Ke Tang, Pu Wang, Alexandre Devert, and Xin Yao. Frequency Fitness Assignment. IEEE Transactions on Evolutionary Computation (IEEE-EC), 18(2):226-243, April 2014. https://dx.doi.org/10.1109/TEVC.2013.2251885 Thomas Weise, Yan Chen, Xinlu Li, and Zhize Wu. Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. Applied Soft Computing Journal (ASOC), 92:106269, June 2020. https://dx.doi.org/10.1016/j.asoc.2020.106269 Thomas Weise, Xinlu Li, Yan Chen, and Zhize Wu. Solving Job Shop Scheduling Problems Without Using a Bias for Good Solutions. In Genetic and Evolutionary Computation Conference Companion (GECCO’21 Companion), July 10-14, 2021, Lille, France. ACM, New York, NY, USA. ISBN 978-1-4503-8351-6. https://dx.doi.org/10.1145/3449726.3463124 Thomas Weise, Mingxu Wan, Ke Tang, and Xin Yao. Evolving Exact Integer Algorithms with Genetic Programming. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’14), Proceedings of the 2014 World Congress on Computational Intelligence (WCCI’14), pages 1816-1823, July 6-11, 2014, Beijing, China. Los Alamitos, CA, USA: IEEE Computer Society Press. ISBN: 978-1-4799-1488-3. https://dx.doi.org/10.1109/CEC.2014.6900292 A fitness representing the rank of a solution based on its quality. First, all solutions are sorted based on their objective values. Then, they receive their rank, i.e., index+1 in the sorted list, as fitness. If two elements have the same objective value, they also receive the same rank. This rank will be the index+1 of the first element. Together with fitness proportionate selection ( L. Darrell Whitley. The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best. In J. David Schaffer, ed., Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA’89), June 4-7, 1989, Fairfax, VA, USA, pages 116-121. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. ISBN: 1-55860-066-3 https://www.researchgate.net/publication/2527551 Tobias Blickle and Lothar Thiele. A Comparison of Selection Schemes used in Genetic Algorithms. Second edition, December 1995. TIK-Report 11 from the Eidgenössische Technische Hochschule (ETH) Zürich, Department of Electrical Engineering, Computer Engineering and Networks Laboratory (TIK), Zürich, Switzerland. ftp://ftp.tik.ee.ethz.ch/pub/publications/TIK-Report11.ps Bases: A fitness computing the rank of an individual based on its quality. Assign the rank as fitness. A fitness combining the rank of a solution with the iteration of its creation. This fitness assignment process is compatible with the simple (mu+lambda) Evolutionary Algorithm implemented in Bases: A fitness joining objective rank and creation iteration. The fitness assignment strategy will use two pieces of information to determine the fitness of a solution: the rank the solutions by their objective values ( the iteration index ( It will multiply the rank of the solution with the range of the iteration index in the population and then add the maximum iteration index minus the iteration index of the solution, i.e., fitness(x) = rank(f(x)) * (max_it - min_it + 1) + (max_it - it(x)) This way, better solutions receive better fitness and ties are broken such that younger solutions (with higher iteration index) are preferred. In combination with best selection (GeneralEA. The transform objective values to scalar fitness values that are then used by Selection algorithms.Submodules¶
moptipy.algorithms.so.fitnesses.direct module¶
FitnessProportionateSUS), it turns an EA (GeneralEA) to a minimization variant of the traditional Genetic Algorithms.FitnessRankAndIteration, which is the default fitness assignment strategy. It is therefore also not compatible to our basic (mu+lambda) Evolutionary Algorithm implementation (EA).moptipy.algorithms.so.fitnesses.ffa module¶
it) of the solutions into the fitness. This index is used to break ties, in which case newer solutions are preferred.moptipy.algorithms.so.fea1plus1.FEA1plus1 if “best” selection (moptipy.algorithms.modules.selections.best.Best) is used at mu=lambda=1. To facilitate this, there is one special case in the FFA fitness assignment: If the population consists of exactly 1 element at iteration index 0, then the frequency values are not updated.moptipy.algorithms.so.fitnesses.rank module¶
>>> # The first value in FRecord(x, y) is the solution, which is not matter
>>> # here. The second value is the objective value used for ranking.
>>> l = [FRecord(1, 10), FRecord(2, 3), FRecord(3, 3), FRecord(4, 2)]
>>> from numpy.random import default_rng
>>> Rank().assign_fitness(l, default_rng())
>>> for z in l:
... print(f"x={z.x}, fitness={z.fitness}")
x=4, fitness=1
x=2, fitness=2
x=3, fitness=2
x=1, fitness=4
FitnessProportionateSUS), it works very similar to linear ranking selection in an EA (GeneralEA).Fitness>>> l = [FRecord(0, 10), FRecord(1, 5), FRecord(2, 5), FRecord(3, -1)]
>>> from numpy.random import default_rng
>>> Rank().assign_fitness(l, default_rng())
>>> l[0].x
3
>>> l[0].fitness
1
>>> l[1].x
1
>>> l[1].fitness
2
>>> l[2].x
2
>>> l[2].fitness
2
>>> l[3].x
:rtype: :sphinx_autodoc_typehints_type:`\:py\:obj\:\`None\``
0
>>> l[3].fitness
4
moptipy.algorithms.so.fitnesses.rank_and_iteration module¶
EA. It will assign a better fitness to a solution which has a better objective value. Ties will be broken based on the iteration counter it of the solution records Record.Fitnessf). If two solutions have the same fitness, they get the same rank, but the next-worst solution will then get a rank with is larger by 2.it) relative to the maximum and minimum iteration index.moptipy.algorithms.modules.selections.best.Best), this replicates the behavior of our simple (mu+lambda) Evolutionary Algorithm (EA).