………………………………………………………………………………2.Abstract 6… [612297]

1

1.Introduction 5
………………………………………………………………………………2.Abstract 6
……………………………………………………………………………………3.Genetic Algorithms 7
…………………………………………………………………..3.1 History of genetic algorithms 7
………………………………………………………………….3.2 Initialization 8
………………………………………………………………………………………….3.2.1 Number of solutions 8
……………………………………………………………………….3.2.2 The correct solution 9
……………………………………………………………………….3.3 Types of Representation 9
………………………………………………………………………..3.3.1 Binary Representations 9
…………………………………………………………………..3.3.2 Integer Representation 10
………………………………………………………………….3.3.3 Real-valued Representations 11
…………………………………………………………3.3.4 Messy Representations 11
…………………………………………………………………3.4 Selection 11
…………………………………………………………………………………………..3.4.1 Roulette Wheel Selection (RWS) 12
…………………………………………………….3.4.2 Stochastic Universal Sampling (SUS) 13
……………………………………………..3.4.3 Linear Rank Selection (LRS) 13
…………………………………………………………..3.4.4 Exponential Rank Selection (ERS) 14
…………………………………………………..3.4.5 Tournament Selection 15
…………………………………………………………………..3.4.6 Truncation Selection 16
……………………………………………………………………..3.5 Genetic Operators 17
………………………………………………………………………………3.5.1 Crossover 17
……………………………………………………………………………………3.5.1.1 Single Point Crossover 17
……………………………………………………………3.5.1.2 Double Point Crossover 18
………………………………………………………….3.5.1.3 Uniform Crossover 18
…………………………………………………………………3.5.1.4 Arithmetic Crossover (floating point only) 19
………………………………….3.5.1.5 Heuristic Crossover (floating point only) 19
……………………………………3.5.2 Mutation 20
……………………………………………………………………………………..3.5.2.1 Uniform Mutation 20
…………………………………………………………………..3.5.2.2 Non-uniform Mutation (floating point only) 21
………………………………..3.5.2.3 Boundary Mutation (floating point only) 22
…………………………………….3.5.2.4 Creep Mutation (floating point only) 22
………………………………………….3.6 Final Results 23
………………………………………………………………………………………4.Smart fit iPhone application 25
………………………………………………………4.1 Core features 25
……………………………………………………………………………………..2

5.Conclusion 27
……………………………………………………………………………..5.Bibliography 28……………………………………………………………………………
3

4

1.Introduction
5

2.Abstract
6

3.Genetic Algorithms 3.1 History of genetic algorithms Several computer scientists studied evolutionary systems with the idea that evolution could be used as an optimization tool for engineering problems. The idea in all of these problems was to evolve a population of candidate solutions using operators inspired by natural genetic variation and natural selection. In the 1960s, Rechenberg(1965, 1973) introduced “evolution strategies”( Evolutionsstrategie in the original German), a method he used to optimize real-valued parameters for devices such as airfoils. This idea was then continued by Schwefel (1975, 1977). Evolution strategy has remained an active area of research, mostly developing independently from the field of genetic algorithms. Genetic Algorithms are the most widely known type of Evolutionary Algorithms, now receiving remarkable attention among every software developer. Probably the earliest predecessor of these algorithms emerged in the work of Fraser, a biologist who wanted to simulate evolution with special emphasis on the interaction of epistasis with selection. In the 1960s, genetic algorithms(GAs) were invented by John Holland and were developed by his students and colleagues at the University of Michigan in the 1960s and the 1970s. Hollands original goal was not to design algorithms to solve specific problems, but rather to formally study the phenomenon of adaptation as it occurs in nature and to develop ways in which the mechanisms of natural adaptation might be imported into computer systems. In one of his books, “Adaptation in Natural and Artificial Systems” he described the genetic algorithm as an abstraction of biological evolution and gave a theoretical framework for adaptation under the GA.! Holland himself pointed out how to interpret his reproductive plans in terms of genetics, economics, game-playing, pattern recognition, statistical inference, control, and parameter optimization. [1]7

3.2 Initialization 3.2.1 Number of solutions The idea of searching among a collection of candidate solutions for a desired solution is so common in computer science that is has been given its own name: searching in a “search space”. Here the term “search space” refers to some collection of candidate solutions to a problem. Most often one is looking for the best solution in a specific set of solutions. The space of all feasible solutions (the set of solutions where the desired solution is contained) is also called the “state space”. Each and every point in the search represents a possible solution of the problem. Therefore each possible solution can be “marked” by its fitness value, depending on the definition of the given problem. With Genetic Algorithm one looks for the best solution among a number of possible solutions represented by one point in the search space. The difficulties in this ease are the local minima and the starting point of the search.
Fig.1: Example of a search space 8

Genetic Algorithm are seen as algorithms with some interesting features: first they are a stochastic algorithm, randomness has an essential role in Genetic Algorithms. Both selection and reproduction needs random procedures. A second very important point is the fact that genetic algorithms will always consider a group, collection, of solutions named population. By keeping in memory more than one solution at a time, this algorithms are presented with some benefits. The algorithm can recombine different, previous, solutions to get better ones with each iteration thus using the benefits of assortment. A population base algorithm is also opened to parallelization. 3.2.2 The correct solution Genetic algorithms are iterated until the fitness value of the “best-so-far” chromosome stabilizes and the later iterations will start providing less and less improvements. This means the algorithm has converged to a solution. The whole process of iterations is called a run. At the end of each run there is usually at least one chromosome that is a highly fit solution to the original problem. Depending on how the algorithm is written, this could be the most fit of all the “best-so-far” chromosomes, or the most fit of the final generation. The “performance” of a genetic algorithm depends highly on the method used to encode candidate solutions into chromosomes and “the particular criterion for success,” or what the fitness function is actually measuring. Other important details are the probability of crossover, the probability of mutation, the size of the population, and the number of iterations. These values can be adjusted after assessing the algorithm’s performance on a few trial runs. 3.3 Types of Representation 3.3.1 Binary Representations Binary representations are the most widely used representations for selectorecombinative GAs. Selectorecombinative GAs use crossover as the 9

primary search operator, and process schemata. In this types of GAs, mutation only serves as background noise to the algorithm. The search space ! is denoted by !, where ! is the length of a binary vector !. When using binary representations the genotype-phenotype mapping ! is dependent on the specific type of problems that is desired to be solved. For many combinatorial optimization problems, binary representation is seen as a very natural way of encoding the problem. Specific genotype-phenotype mappings are necessary when encoding integer problems using the binary representation. Different types of binary representations for integers assign the integers ! (phenotypes) in a different way to the binary vectors ! (genotypes). The most common representations are the binary, Gray, and unary encoding. When encoding continuous variables by using binary vectors, the number of bits that are used to represent a phenotype continuous variable gives the accuracy of the representation of the problem. By increasing the number of bits that are used for representing one continuous variable, the accuracy of the representation can be increased. The maximal accuracy that we can obtain when encoding a continuous phenotypic variable ! by using a binary vector of length ! is !. 3.3.2 Integer Representation Instead of using binary strings with cardinality !, where !, we can use higher !-ary alphabets for the genotypes. Then, instead of a binary alphabet, a !-ary alphabet is used for the string of length !. We are able to encode ! different possibilities, as opposed to binary representation where we can encode only ! different individuals. The size of the search space increases from! to !. ϕgϕg={0,1}llxg=(xg1,…xgl)∈{0,1}lfg
xp∈ϕpxg∈ϕg
xp∈[0,1]l1/2l+1X=2x∈{N+∖{0,1}}XXlXl2l|ϕg|=2l|ϕg|=Xl10

In many integer problems, it is often preferred to use binary instead of integer representations thus allowing maximum schema processing with binary alphabets when using some of the standard recombination operators. 3.3.3 Real-valued Representations When using real-valued representations, the search space ! is defined as !, where ! is the length of the real-valued chromosome. When using real-valued representations, researches often favor mutation-based GAs. Real-valued representations can not exclusively be used for encoding real-valued problems, but also for other permutation and combinatorial problems. Trees, schedules, tours, or other combinatorial problems can easily be represented by using real-valued vector and special genotype-phenotype mappings. 3.3.4 Messy Representations In all the previously presented representations, the position of each allele is fixed along the chromosome and only the corresponding value is specified. The first gene-independent representation was proposed by Holland (1975). He proposed the inversion operator which changes the relative order of the alleles in the string. The position of an allele and the corresponding value are coded together as a tuple in a string. This type of representation can be used for binary, integer, and real-valued representations and allows an encoding which is independent of the position of the alleles in the chromosome. Later, Goldberg (1989) used this position-independent representation for the messy genetic algorithm. 3.4 Selection In the Genetic Algorithms world there are six selection methods: the roulette wheel selection (RWS), the stochastic universal sampling (SUS), the linear rank ϕgϕg=ℝll
11

selection (LRS), the exponential rank selection (ERS), the tournament selection (TOS), and the truncation selection (TRS) [3]. 3.4.1 Roulette Wheel Selection (RWS) The conspicuous characteristic of this selection method is the fact that it gives each individual I of the current population a probability p(i) of being selected, proportional to its fitness f(): ! when n denotes the population size in terms of the number of individuals. The RWS can be implemented according to the following pseudo-code: RWS_pseudo-code {
Calculate the sum !
For each individual ! do { – Generate a random number !; – ! – Do { – ! – ! } while (! and !) – Select the individual j; } } Note that a well-known drawback of this technique is the risk of premature convergence of the GA to a local optimum, due to the possible presence of a dominant individual that always wins the competition and is selected as a parent. p(i)=f()∑nj=if(j)
S=n∑j=if(j)1≤i≤na∈[0,S]iSum=0;j=0;iSum←iSum+f(j);j←j+1;iSum<αj<n
12

3.4.2 Stochastic Universal Sampling (SUS) The Stochastic Universal Sampling is a variant of RWS aimed at reducing the risk of premature convergence. It can be implemented according to the following pseudo-code: SUS_pseudo-code {
Calculate the mean !
Generate a random number !
!
Do { – If (!) { – select the ! individual; – ! } else { – ! – ! } } while (!) } 3.4.3 Linear Rank Selection (LRS) LRS is also a variant of RWS that tries to overcome the drawback of premature convergence of the GA to a local optimum. It is based on the rank of individuals rather than on their fitness. The rank n is accorded to the best individual whilst the ¯f=1/nn∑i=1f(i)α∈[0,1];Sum=f(1);delta=αׯf;j=0;delta<Sumjthdelta=delta+Sum;j=j+1;Sum=Sum+f(j);j<n
13

worst individual gets the rank 1. Thus, based on its rank, each individual I has the probability of being selected given by the expression: ! Once all individuals of the current population are ranked, the LRS procedure can be implemented according to the following pseudo-code: LRS_pseudo-code {
Calculate !
For each individual ! do { – Generate a random number ! – For each ! do { – If (!) { – Select the ! individual; – Break; } } } } 3.4.4 Exponential Rank Selection (ERS) The ERS is based on the same principle as LRS, but it differs from LRS by the probability of selecting each individual. For ERS, this probability is given by the expression: ! with ! p(i)=rank(i)n×(n−1)
v=1n−2.001;1≤i≤nα∈[0,v];1≤j≤np(j)≤αjth
p(i)=1.0*exp(−rank(i)c)c=(n*2*(n−1))(6*(n−1)+n)14

Once the n probabilities are computed, the rest of the method can be described by the following pseudo-code: ERS_pseudo-code {
For each individual ! do { – Generate a random number ! – For each ! do { – Select the ! individual; – Break; } } } 3.4.5 Tournament Selection Tournament selection is a variant of rank-based selection methods. Its principle consists in randomly selecting a set of k individuals. These individuals are then ranked according to their relative fitness and the fittest individual is selected for reproduction. The whole process is repeated n times for the entire population. Hence, the probability of each individual to be selected is given by the expression: ! Technically speaking, the implementation of TOS can be performed according to the pseudo-code: TSO_pseudo-code {
Create a table t where the n individuals are placed in a randomly chosen order 1≤i≤nα∈[19c,2c];1≤j≤njth
p(i)={Ck−1n−1ifi∈[1,n−k−1]0ifi∈[n−k,n]
15

For ! do { – For ! do { – ! – For ! do { – ! – If (!) { – select i1 } else { – select i2 } } – ! } } } 3.4.6 Truncation Selection The truncation selection is a very simple technique that orders the candidate solutions of each population according to their fitness. Then, only a certain portion p of the fittest individuals are selected and reproduced 1/p times. It is less used in practice than other techniques, except for very large population. The pseudo-code of the technique is as follows: TRS_pseudo-code {
Order the n individuals of P(t) according to their fitness;
Set the portion p of individuals to select;
!
Select the first sp individuals; } 1≤i≤n1≤j≤ni1=t(j);1≤m≤ni2=t(j+m);f(i1)>f(i2)
j=j+k;
sp=abs(n×p);16

3.5 Genetic Operators After parents have been select through one of the methods introduced above, they are randomly paired. The genetic operators are then applied on these paired parents to produce offspring. These are two main categories of operators: crossover and mutation. 3.5.1 Crossover The purpose of crossover is to vary the individual quality by combining the desired characteristics from two parents. Over the years, numerous variants of crossover have been developed in the GA literature, and comparisons also have been made among these methods. However, most of these studies rely on a small set of test problems, and thus it is hard to draw a general conclusion on which method is better than others. 3.5.1.1 Single Point Crossover
This is the traditional and the simplest way of crossover: a position is randomly chosen as the crossover point and the segment of the parents after the point are exchanged to form two offspring. The position can be anywhere between the first and the last allele. For example, let us suppose position 2 is the crossover point, the process is shown in the following table. Please note that ! or ! stands for a bit for bit-string chromosomes; whereas for floating point chromosomes, it stands for a floating point variable. xiyi
17

Single point crossover has several drawbacks. One of them is the so-called positional bias: the single point combination of this method can’t create certain schemas. The other is the endpoint effect – the end point of the two parents is always exchanged, which is unfair to other points. 3.5.1.2 Double Point Crossover
In this crossover method, two positions are randomly chosen and the segments between them are exchanged. For instance, assuming position 2 and 5 are chosen as crossover points, the process is shown in the following table. Compared with single point crossover, double point crossover is able to combine more schemas and eliminate the ending point effect. But similar to single point crossover, there are some schemas that it can’t create. 3.5.1.3 Uniform Crossover
As a natural extension to single and double point crossover, uniform crossover allows each allele in the parents to be exchanged with a certain probability p. For example, given !, and the series of random numbers drawn for alleles 1 to 6 are: 0.4, 0.7, 0.3, 0.8, 0.9, 0.5, the results will be: Since any point in the parent can be exchanged, uniform crossover can recombine any schemas. However, this advantage comes at cost. The random bit exchange p=0.6
18

may prevent the forming of valuable building blocks (short and highly fit segments that are able to form strings of potentially higher fitness through recombination), because the random exchange of uniform crossover can be highly disruptive to any evolution schemas. 3.5.1.4 Arithmetic Crossover (floating point only)
The above crossover methods work fine for the bit-string representation. However, there is a problem when applying them to floating-point encoding: the crossed parameter values in the parents are propagated to their offspring unchanged, only in different combinations. In other words, no new parameter values are introduced. To address this problem, GA researchers introduced arithmetical crossover: the ! parameter in offspring, !, is a linear combination of the ! parameters of two parents, ! and !, i.e., ! where a is a random value in the interval [0,1]. This linear formula guarantees that the value of the newly created offspring is always within the domain of the problem. For example, suppose the crossover happens at position 2 and 5, the resultant offspring are given in the table bellow: 3.5.1.5 Heuristic Crossover (floating point only)
Heuristic crossover uses the values of the fitness function to determine the direction of search according to the following formula: ithZiithXiYiZi=aXi+(1−a)Yi
19

! where a is also a random value in the interval [0,1]; X and Y are the parental parameter vectors; f(X) and f(Y) are the fitness function values. Contrary to arithmetic crossover which always creates offspring within the range of their parents, heuristic crossover always generates offspring outside of the range of the parents. Sometimes the offspring values are so far away from their parents that they get beyond the allowed range of that variable. In such a case, the offspring is discarded and a new a is tried and a new offspring created. If after a specified number times no feasible offspring is generated, the operator quits with no offspring produced. 3.5.2 Mutation Mutation is another essential operator of genetical algorithm. The idea behind mutation is to introduce diversity into the population and thus prevent the premature convergence. Like crossover, GA researchers have developed numerous variants of mutation method over GA history. Since every method has its strength and weakness, it is still an open question as to claim which method is the best. 3.5.2.1 Uniform Mutation
This is the conventional method of mutation, in which each allele has an equal opportunity to be mutated. For each allele, a random number ! is generated and then compared with the mutation rate ! (a user specified parameter), if !, then this allele is mutated; otherwise, stays unchanged. For the binary encoding, either bit-string or Gray-coded integer, the mutation simply flips the bit from 0 to 1 or vice versa. For floating-point encoding, the allele is replaced with a random value within the domain of that variable. For example, if ! is selected for mutation in the chromosome X = [3.221, 4.556, Z={a(Y−X)+Yiff(Y)≤f(X)a(X+Y)+Xotherwise
rpmr>pm
x220

2.341, 5.897], and the domain of ! is [3.000, 5.5000], then the chromosome after mutation may be X=[3.221, 3.938, 2.341, 5.897]. 3.5.2.2 Non-uniform Mutation (floating point only)
To increase the fine tuning of the chromosome and reduce the randomness of uniform mutation, Michalewicz presented a dynamic mutation operator called non-uniform mutation. The mechanism works as follows: if element ! was selected for mutation, the resultant offspring is determined by the following formula, ! where ! is a random number between 0 and 1, ! and ! represent lower and upper bounds of variable !. The function ! is defined by: ! where r is also a random number between 0 and 1, ! is the maximal generation number, and ! is a user-defined system parameter that determines the degree of dependency on iteration number !. This simulated annealing flavored formula returns a value in the range [0, x] such that the probability of ! being close to 0 increases as ! increases. This property guarantees the newly created offspring is in the feasible range. Moreover, it enables the operator to explore the space broadly with an initially large mutation step, but very locally at later stages; thus make the newly generated offspring closer to its predecessor than a randomly generated one. x2
xiZi={xi+△(t,UBi−xi)ifa>0.5xi−△(t,xi−LBi)ifa≤0.5aLBiUBixi△(t,x)△(t,x)=x(1−r(1−t/T)b)Tbt△(t,x)t
21

3.5.2.3 Boundary Mutation (floating point only)
Boundary Mutation is a variant of uniform mutation. In uniform mutation, the newly generated allele is a random value within the domain of that allele. In boundary mutation, however, the newly generated allele is either the upped bound or the lower bound of the domain, with equal probability, i.e., ! where the parameters have the same meaning as in non-uniform mutation. This mutation operator is extremely functional in optimizing problems where the optimal solution either lies on or near the boundary of the constrained search space. In addition, the conjunction of this operator with arithmetic crossover will help counteract the later operator’s “contraction effect” on the population. However, this operator has obvious disadvantages for many problems. 3.5.2.4 Creep Mutation (floating point only)
Davis introduced the creep mutation in his GA handbook, in which the allele values which are to be mutated are incremented or decremented by the creep fraction – the fraction of the valid range for that variable’s value. The selected variable ! is mutated according to the following formula: ! where ! and ! are the upper bound and the lower bound of the variable’s domain respectively; ! is a random number in the range [-1, 1]; ! is the creep factor, a user defined number between 0 and 1. It is equally likely that the allele value will be incremented or decremented, and the value is adjusted to the boundary value if the newly generated allele falls out of the valid range of the allele. Zi={UBifa>0.5LBifa≤0.5
xizi=min(iMax,max(iMin,xi+rs(iMax−iMin)))iMaxiMinrs
22

3.6 Final Results A simple Genetic Algorithm will exhibit the following features: finite population, bit representation, one-point crossover, bit-flip mutation and roulette wheel selection. The most widely employed form of GA is the simple GA. In particular, most of the scarce theoretical formalizations of GAs that are available in the literature are focused on simple GAs. For this simple GA we have three traditional termination conditions that have been used throughout the years: – An upper limit on the number of generations is reached. – An upper limit on the number of evaluations of the fitness function is reached, or – The chance of achieving significant changes in the next generations is excessively low. In comparison to the third option, the first one requires some knowledge about the problem in order to estimate a reasonable maximum search length. In this case there are two variants, namely genotypical and phenotypical termination criteria. The former end when the population reaches certain convergence levels with respect to the chromosomes in the population, in short, the number of genes that have converged to a certain value of the allele is checked. The convergence or divergence of a gene to a certain allele is established by the GA designer through the definition of a preset percentage, which is a threshold that should be reached. Unlike the genotypical approach, phenotypical termination criteria measure the progress achieved by the algorithm in the last n generations, where n is a value preset by the GA designer. When this measurement, which may be expressed in terms of the average fitness value for the population, yields a value beyond a certain limit !, it is said that the algorithm has converged and the evolution is immediately interrupted. Whatever the problem, it is nowadays considered inappropriate to employ sets of fixed values for parameters in an evolutionary algorithm. Therefore, it would ϵ23

be unadvisable to choose a termination condition based on a preestablished number of iterations.
24

4.Smart fit iPhone application 4.1 Core features The application features are designed so that each user can get the maximum out of it with ease. The application will offer three big features that are: Allowing to create workout plans for the whole week using the Genetic Algorithm implemented based on different types of workouts and different other preferences that are given as input from the user. The workouts are saved then and displayed on the “My workouts” page. The second feature will be a “My diet” page where the user can create meal plans for the whole week again using the same Genetic Algorithm that is implemented depending on different options that will be available (eg “lose weight”, “gain weight”…). The third and last feature will be a page called “What’s this” where the user can take a picture of something (eg “banana”, “apple”, “steak”) and the application will prompt the user with the information of that specific object scanned like nutrition facts and possibility of adding it to a meal plan or even start a new one around it. 25

26

5.Conclusion file:///Users/danielguramulta/Documents/LNAI3171_405413.pdf 27

5.Bibliography 1.Goldberg, D. E. 1989. Genetic algorithms in search, optimization and machine learning. Addison-Wesley. 2.MASKREY , Molly; WANG, Wallace. Using Machine Learning. In: Pro iPhone Development with Swift 4. Apress, Berkeley, CA, 2018. p. 255-283. 3.Hancock. P, “A comparison of selection mechanisms”, . In Handbook of Evolutionary Computation, Eds . IOP Publishing and Oxford University Press., Bristol, UK, 1997 4.Michalewicz. Z, “Genetic Algorithms + Data Structure = Evolution Programs”, Third Edition, Springer, 2007 5.DeJong. K. A, “Evolutionary Computation : a unified approach”, MIT Press, 2007. 6.Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, USA, 1975. 28

7.Thomas Bäck, Evolutionary algorithms in theory and practice_ evolution strategies, evolutionary programming, genetic algorithms-Oxford University Press (1996).
29