Genetic algorithm - Revision history

Fall2024 Wiki Team3 Alter: /* 2.8 Repeat Steps 2.3-2.7 */

2024-12-16T03:27:07Z

2.8 Repeat Steps 2.3-2.7

← Older revision		Revision as of 23:27, 15 December 2024
Line 398:		Line 398:

	==== 2.8 Repeat Steps 2.3-2.7 ====		==== 2.8 Repeat Steps 2.3-2.7 ====
	Using the code to perform the repeating process for 50 more generations we got		Using the code (https://github.com/AcidHCL/CornellWiki) to perform the repeating process for 50 more generations we got

	[[File:output.png\|800x498px\|Fig.2. 50 iteration results]]		[[File:output.png\|800x498px\|Fig.2. 50 iteration results]]

Fall2024 Wiki Team3 Alter: /* Algorithm Discussion */

2024-12-15T02:43:15Z

Algorithm Discussion

← Older revision		Revision as of 22:43, 14 December 2024
Line 24:		Line 24:
	#* Evaluate the fitness of every chromosome in the population to see how good it is. Higher fitness implies better solution, making the chromosome more likely to be selected as a parent of next generation		#* Evaluate the fitness of every chromosome in the population to see how good it is. Higher fitness implies better solution, making the chromosome more likely to be selected as a parent of next generation
	# Selection		# Selection
	#* Natural selection serves as the main inspiration of GA, where chromosomes are randomly selected from the entire population for mating, and chromosomes with higher fitness values are more likely to be selected <ref name="Mirjalili"> Mirjalili, S. (2018). Genetic Algorithm. Evolutionary Algorithms and Neural Networks, Springer, pp. 43–56 </ref>.		#* Natural selection serves as the main inspiration of GA, where chromosomes are randomly selected from the entire population for mating, and chromosomes with higher fitness values are more likely to be selected<ref name="Mirjalili"> Mirjalili, S. (2018). Genetic Algorithm. Evolutionary Algorithms and Neural Networks, Springer, pp. 43–56 </ref>.
	# Crossover		# Crossover
	#* The purpose of crossover is to create superior offspring (better solutions) by combining parts from each selected parent chromosome. There are different types of crossover, such as single-point and double-point crossover <ref name="Mirjalili" />. In single-point crossover, the parent chromosomes are swapped before and after a single point. In double-point crossover, the parent chromosomes are swapped between two points <ref name="Mirjalili" />.		#* The purpose of crossover is to create superior offspring (better solutions) by combining parts from each selected parent chromosome. There are different types of crossover, such as single-point and double-point crossover<ref name="Mirjalili" />. In single-point crossover, the parent chromosomes are swapped before and after a single point. In double-point crossover, the parent chromosomes are swapped between two points<ref name="Mirjalili" />.
	# Mutation		# Mutation
	#* A mutation operator is applied to make random changes to the genes of children's chromosomes, maintaining the diversity of the individual chromosomes in the population and enabling GA to find better solutions<ref name="Mirjalili" />.		#* A mutation operator is applied to make random changes to the genes of children's chromosomes, maintaining the diversity of the individual chromosomes in the population and enabling GA to find better solutions<ref name="Mirjalili" />.
Line 40:		Line 40:
	Steps 3-5 in GA involves techniques of changing the genes of chromosomes to create new generations. The functions that were applied to the populations are called genetic operators. The main types of GA operators include selection operator, crossover operator, and mutation operator. Below are some widely used operators:		Steps 3-5 in GA involves techniques of changing the genes of chromosomes to create new generations. The functions that were applied to the populations are called genetic operators. The main types of GA operators include selection operator, crossover operator, and mutation operator. Below are some widely used operators:
	# Selection Operator		# Selection Operator
	#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation <ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.		#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation<ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.
	# Crossover Operator		# Crossover Operator
	#* Single-point and double-point crossover operators were introduced in the algorithm above, and there is also a k-point crossover that selects multiple points and swaps the segments between those points of the parent chromosomes to generate new offspring <ref name="Katoch" />. Some other well-known crossover operators are uniform crossover, partially matched crossover, order crossover, and shuffle crossover <ref name="Katoch" />.		#* Single-point and double-point crossover operators were introduced in the algorithm above, and there is also a k-point crossover that selects multiple points and swaps the segments between those points of the parent chromosomes to generate new offspring<ref name="Katoch" />. Some other well-known crossover operators are uniform crossover, partially matched crossover, order crossover, and shuffle crossover<ref name="Katoch" />.
	# Mutation Operator		# Mutation Operator
	#* Mutation operator introduces variability into the population that helps the algorithm to find the global optimum. Displacement mutation operator randomly choose a substring from an individual and insert it into a new position <ref name="Katoch" />. Additionally, other prominent mutation operators are simple inversion mutation, scramble mutation, binary bit-flipping mutation, directed mutation, and others <ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>.		#* Mutation operator introduces variability into the population that helps the algorithm to find the global optimum. Displacement mutation operator randomly choose a substring from an individual and insert it into a new position<ref name="Katoch" />. Additionally, other prominent mutation operators are simple inversion mutation, scramble mutation, binary bit-flipping mutation, directed mutation, and others<ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>.

	== Numerical Example ==		== Numerical Example ==

Fall2024 Wiki Team3 Alter: /* Algorithm Discussion */

2024-12-15T02:35:09Z

Algorithm Discussion

← Older revision		Revision as of 22:35, 14 December 2024
Line 42:		Line 42:
	#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation <ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.		#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation <ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.
	# Crossover Operator		# Crossover Operator
	Single-point and double-point crossover operators were introduced in the algorithm above, and there is also a k-point crossover that selects multiple points and swaps the segments between those points of the parent chromosomes to generate new offspring <ref name="Katoch" />. Some other well-known crossover operators are uniform crossover, partially matched crossover, order crossover, and shuffle crossover <ref name="Katoch" />.		#* Single-point and double-point crossover operators were introduced in the algorithm above, and there is also a k-point crossover that selects multiple points and swaps the segments between those points of the parent chromosomes to generate new offspring <ref name="Katoch" />. Some other well-known crossover operators are uniform crossover, partially matched crossover, order crossover, and shuffle crossover <ref name="Katoch" />.
	# Mutation Operator		# Mutation Operator
	Mutation operator introduces variability into the population that helps the algorithm to find the global optimum. Displacement mutation operator randomly choose a substring from an individual and insert it into a new position <ref name="Katoch" />. Additionally, other prominent mutation operators are simple inversion mutation, scramble mutation, binary bit-flipping mutation, directed mutation, and others <ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>.		#* Mutation operator introduces variability into the population that helps the algorithm to find the global optimum. Displacement mutation operator randomly choose a substring from an individual and insert it into a new position <ref name="Katoch" />. Additionally, other prominent mutation operators are simple inversion mutation, scramble mutation, binary bit-flipping mutation, directed mutation, and others <ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>.

	== Numerical Example ==		== Numerical Example ==

Fall2024 Wiki Team3 Alter at 02:33, 15 December 2024

2024-12-15T02:33:57Z

← Older revision		Revision as of 22:33, 14 December 2024
Line 37:		Line 37:

	Genetic Operators:		Genetic Operators:

	Steps 3-5 in GA involves techniques of changing the genes of chromosomes to create new generations. The functions that were applied to the populations are called genetic operators. The main types of GA operators include selection operator, crossover operator, and mutation operator. Below are some widely used operators:		Steps 3-5 in GA involves techniques of changing the genes of chromosomes to create new generations. The functions that were applied to the populations are called genetic operators. The main types of GA operators include selection operator, crossover operator, and mutation operator. Below are some widely used operators:
	# Selection Operator		# Selection Operator
	#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation <ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.		#* Some famous selection operators include roulette wheel, rank, tournament, etc. Roulette wheel selection allocates strings onto a wheel based on their fitness value, then randomly selects solutions for the next generation <ref name="Katoch"> Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 </ref>.
	# Crossover Operator		# Crossover Operator
			Single-point and double-point crossover operators were introduced in the algorithm above, and there is also a k-point crossover that selects multiple points and swaps the segments between those points of the parent chromosomes to generate new offspring <ref name="Katoch" />. Some other well-known crossover operators are uniform crossover, partially matched crossover, order crossover, and shuffle crossover <ref name="Katoch" />.
	# Mutation Operator		# Mutation Operator
			Mutation operator introduces variability into the population that helps the algorithm to find the global optimum. Displacement mutation operator randomly choose a substring from an individual and insert it into a new position <ref name="Katoch" />. Additionally, other prominent mutation operators are simple inversion mutation, scramble mutation, binary bit-flipping mutation, directed mutation, and others <ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>.
	<ref> Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., & Leong, K. Y. (2017). Crossover and mutation operators of genetic algorithms. International journal of machine learning and computing, 7(1), 9-12 </ref>

	== Numerical Example ==		== Numerical Example ==

Fall2024 Wiki Team3 Alter: /* Algorithm Discussion */

2024-12-15T02:26:33Z

Algorithm Discussion

@@ Line 35: / Line 35: @@
 #* No significant improvement from newer generations
 #* Expected fitness value is achieved
 == Numerical Example ==

Fall2024 Wiki Team3 Alter at 03:15, 14 December 2024

2024-12-14T03:15:47Z

@@ Line 10: / Line 10: @@
 == Algorithm Discussion ==
 The GA was first introduced by John H. Holland<ref name=":2"> Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), 88–105 </ref> in 1973. It is an optimization technique based on Charles Darwin’s theory of evolution by natural selection.
 [[File:GA.drawio.png|thumb|501x501px|Fig.1. Flowchart for GA]]

Fall2024 Wiki Team3 Alter at 03:14, 14 December 2024

2024-12-14T03:14:12Z

Show changes

Fall2024 Wiki Team3 Alter at 03:13, 14 December 2024

2024-12-14T03:13:27Z

Show changes

Fall2024 Wiki Team3 Alter: /* Software tools and platforms that utilize Genetic Algorithms */

2024-12-14T03:10:55Z

Software tools and platforms that utilize Genetic Algorithms

← Older revision		Revision as of 23:10, 13 December 2024
Line 417:		Line 417:
	While using GE to forecast financial market indices, people need to import processed historical stock price data. GE will learn price patterns in this data and generate models which can predict future price movements. These models can help traders and analysts identify the trend of the financial market, such as upward and downward trends.		While using GE to forecast financial market indices, people need to import processed historical stock price data. GE will learn price patterns in this data and generate models which can predict future price movements. These models can help traders and analysts identify the trend of the financial market, such as upward and downward trends.

	=== ~~'''~~Software tools and platforms that utilize Genetic Algorithms~~'''~~ ===		=== Software tools and platforms that utilize Genetic Algorithms ===
	'''MATLAB''': The Global Optimization Toolbox of MATLAB is widely used for engineering simulations and machine learning.		'''MATLAB''': The Global Optimization Toolbox of MATLAB is widely used for engineering simulations and machine learning.

Fall2024 Wiki Team3 Alter: /* 1.3 Generation 2 */

2024-12-14T03:10:38Z

1.3 Generation 2

← Older revision		Revision as of 23:10, 13 December 2024
Line 167:		Line 167:
	\| 00110 \|\| <math>6</math> \|\| <math>36</math>		\| 00110 \|\| <math>6</math> \|\| <math>36</math>
	\|}		\|}
	==== ~~'''~~1.3 Generation 2~~'''~~ ====		==== 1.3 Generation 2 ====
	===== 1.3.1 Evaluation =====		===== 1.3.1 Evaluation =====
	Calculate the fitness values:		Calculate the fitness values:
Line 248:		Line 248:
	\| 11011 \|\| <math>27</math> \|\| <math>729</math>		\| 11011 \|\| <math>27</math> \|\| <math>729</math>
	\|}		\|}

	==== 1.4 Conclusion ====		==== 1.4 Conclusion ====
	After 2 iterations, the best optimal solution we find is <math>f = 729, \ x = 27</math>.		After 2 iterations, the best optimal solution we find is <math>f = 729, \ x = 27</math>.