1514123_viral_expt8

KJSCE/IT/LY/SEM VIII/SC/2018-19

Experiment No.: 8 Title: Genetic Algorithm using R

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

Batch: A4

Roll No.: 1514123

Experiment No.: 8

Aim: To implement Genetic Algorithm for expenditure of a month in the wilderness. For the purpose team members will take a backpack along with them. For the adventure individual can take maximum weight up to 20 kilograms. The chart of survival food is given below: Individuals have a number of survival items and each with its own number of “Survival Points”. Item Knife Beans Potatoes Unions Sleeping bag Rope Compass

Survival Point 10 20 15 2 30

Weight in KG 1 5 10 1 7

10 30

5 1

Objective: To achieve maximum number of survival points with Genetic Algorithms.

Resources needed: R , Packages genalg and ggplot2

Theory: Genetic algorithm is a search heuristic. GAs can generate a vast number of possible model solutions and use these to evolve towards an approximation of the best solution of the model. Hereby it mimics evolution in nature.

GA generates a population, the individuals in this population (often called chromosomes) have a given state. Once the population is generated, the state of these individuals is evaluated and graded on their value. The best individuals are then taken and crossed-over – in order to hopefully generate 'better' offspring – to form the new population. In some cases the best individuals in the population are preserved in order to guarantee 'good individuals' in the new generation (this is called elitism). Steps Involved in Genetic Algorithm: 1. Initialisation 2. Fitness Function

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19 3. Selection 4. Crossover 5. Mutation

Pre Lab/ Prior Concepts: Knapsack Algorithms. Concepts : Let’s say, you are going to spend a month in the wilderness. Only thing you are carrying is the backpack which can hold a maximum weight of 30 kg. Now you have different survival items, each having its own “Survival Points” (which are given for each item in the table). So, your objective is maximise the survival points. Here is the table giving details about each item.

Step 1: Initialisation To solve this problem using genetic algorithm, our first step would be defining our population. So our population will contain individuals, each having their own set of chromosomes. We know that, chromosomes are binary strings, where for this problem 1 would mean that the following item is taken and 0 meaning that it is dropped.

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

This set of chromosome is considered as our initial population. Step 2: Fitness Function Let us calculate fitness points for our first two chromosomes. For A1 chromosome [100110],

Similarly for A2 chromosome [001110],

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19 So, for this problem, our chromosome will be considered as more fit when it contains more survival points. Therefore chromosome 1 is more fit than chromosome 2. Step 3: Selection Now, we can select fit chromosomes from our population which can mate and create their off-springs. General thought is that we should select the fit chromosomes and allow them to produce off-springs. But that would lead to chromosomes that are more close to one another in a few next generation, and therefore less diversity. Therefore, we generally use Roulette Wheel Selection method. Don’t be afraid of name, just take a look at the image below.

I suppose we all have seen this, either in real or in movies. So, let’s build our roulette wheel. Consider a wheel, and let’s divide that into m divisions, where m is the number of chromosomes in our populations. The area occupied by each chromosome will be proportional to its fitness value.

Based on these values, let us create our roulette wheel.

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

So, now this wheel is rotated and the region of wheel which comes in front of the fixed point is chosen as the parent. For the second parent, the same process is repeated. Sometimes we mark two fixed point as shown in the figure below.

So, in this method we can get both our parents in one go. This method is known as Stochastic Universal Selection method. Step4: Crossover So in this previous step, we have selected parent chromosomes that will produce off-springs. So in biological terms, crossover is nothing but reproduction. So let us find the crossover of chromosome 1 and 4, which were selected in the previous step. Take a look at the image below.

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

This is the most basic form of crossover, known as one point crossover. Here we select a random crossover point and the tails of both the chromosomes are swapped to produce a new off-springs. If you take two crossover point, then it will called as multi point crossover which is as shown below.

Step 5: Mutation Now if you think in the biological sense, are the children produced have the same traits as their parents? The answer is NO. During their growth, there is some change in the genes of children which makes them different from its parents. This process is known as mutation, which may be defined as a random tweak in the chromosome, which also promotes the idea of diversity in the population. A simple method of mutation is shown in the image below.

So the entire process is summarise as shown in the figure.

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

Source : link The off-springs thus produced are again validated using our fitness function, and if considered fit then will replace the less fit chromosomes from the population. But the question is how we will get to know that we have reached our best possible solution? So basically there are different termination conditions, which are listed below: 1. There is no improvement in the population for over x iterations. 2. We have already predefined an absolute number of generation for our algorithm. 3. When our fitness function has reached a predefined value.

Implementation using R :

Results: (Program printout with output / Document printout as per the format) Program:

install.packages("ggvis") install.packages("e1071") library(genalg) library(ggplot2)

dataset <- data.frame(item = c("pocketknife", "beans", "potatoes", "unions", "sleeping bag", "rope", "compass"), survivalpoints = c(10, 20, 15, 2, 30, 10, 30), weight = c(1, 5, 10, 1, 7, 5, 1)) weightlimit <- 20 chromosome = c(1, 0, 0, 1, 1, 0, 0) dataset[chromosome == 1, ] (Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

dataset cat(chromosome %*% dataset$survivalpoints) evalFunc <- function(x) { current_solution_survivalpoints <- x %*% dataset$survivalpoints current_solution_weight <- x %*% dataset$weight

if (current_solution_weight > weightlimit) return(0) else return(-current_solution_survivalpoints) }

iter = 100 GAmodel <- rbga.bin(size = 7, popSize = 200, iters = iter, mutationChance = 0.01, elitism = T, evalFunc = evalFunc) plot(GAmodel) plot(GAmodel,type = "hist") cat(summary(GAmodel)) solution = c(1, 1, 0, 1, 1, 1, 1) dataset[solution == 1, ] cat(paste(solution %*% dataset$survivalpoints, "/", sum(dataset$survivalpoints)))

animate_plot <- function(x) { for (i in seq(1, iter)) { temp <- data.frame(Generation = c(seq(1, i), seq(1, i)), Variable = c(rep("mean", i), rep("best", i)), Survivalpoints = c(-GAmodel$mean[1:i], -GAmodel$best[1:i])) pl <- ggplot(temp, aes(x = Generation, y = Survivalpoints, group = Variable, colour = Variable)) + geom_line() + scale_x_continuous(limits = c(0, iter)) + scale_y_continuous(limits = c(0, 110)) + geom_hline(y = max(temp$Survivalpoints),lty = 2) + annotate("text", x = 1, y = max(temp$Survivalpoints) + 2, hjust = 0, size = 3, color = "black", label = paste("Best solution:",max(temp$Survivalpoints))) + scale_colour_brewer(palette = "Set1") +opts(title = "Evolution Knapsack optimization model") print(pl) } (Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

} #library(animation) #saveMovie(animate_plot(), interval = 0.1, outdir = getwd()

Output: > dataset <- data.frame(item = c("pocketknife", "beans", "potatoes", "unions", "s leeping bag", "rope", "compass"), survivalpoints = c(10, 20, 15, 2, 30, 10, 30), weight = c(1, 5, 10, 1, 7, 5, 1)) > weightlimit <- 20 > > chromosome = c(1, 0, 0, 1, 1, 0, 0) > dataset[chromosome == 1, ] item survivalpoints weight 1 pocketknife 10 1 4 unions 2 1 5 sleeping bag 30 7 > > > dataset item survivalpoints weight 1 pocketknife 10 1 2 beans 20 5 3 potatoes 15 10 4 unions 2 1 5 sleeping bag 30 7 6 rope 10 5 7 compass 30 1 > > cat(chromosome %*% dataset$survivalpoints) 42> > evalFunc <- function(x) { + + current_solution_survivalpoints <- x %*% dataset$survivalpoints + + current_solution_weight <- x %*% dataset$weight + + + + if (current_solution_weight > weightlimit) + + return(0) else return(-current_solution_survivalpoints) + + } > > > > iter = 100 > > GAmodel <- rbga.bin(size = 7, popSize = 200, iters = iter, mutationChance = 0.0 1, elitism = T, evalFunc = evalFunc) > > plot(GAmodel) > > plot(GAmodel,type = "hist")

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19 > > cat(summary(GAmodel)) GA Settings Type Population size Number of Generations Elitism Mutation Chance

= = = = =

binary chromosome 200 100 TRUE 0.01

Search Domain Var 1 = [,] Var 0 = [,] GA Results Best Solution : 1 1 0 1 1 1 1 > > > solution = c(1, 1, 0, 1, 1, 1, 1) > dataset[solution == 1, ] item survivalpoints weight 1 pocketknife 10 1 2 beans 20 5 4 unions 2 1 5 sleeping bag 30 7 6 rope 10 5 7 compass 30 1 > cat(paste(solution %*% dataset$survivalpoints, "/", sum(dataset$survivalpoints) )) 102 / 117>

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

Questions: 1.

What is genetic Algorithm? State and explain its real world applications.

ANS

    

Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems. Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation.

 (Autonomous College Affiliated to University of Mumbai)

   

KJSCE/IT/LY/SEM VIII/SC/2018-19

In simple words, they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome. Applications of genetic algorithms



Automotive Design Using Genetic Algorithms [GAs] to both design composite materials and aerodynamic shapes for race cars and regular means of transportation (including aviation) can return combinations of best materials and best engineering to provide faster, lighter, more fuel efficient and safer vehicles for all the things we use vehicles for. Rather than spending years in laboratories working with polymers, wind tunnels and balsa wood shapes, the processes can be done much quicker and more efficiently by computer modeling using GA searches to return a range of options human designers can then put together however they please.



Engineering Design Getting the most out of a range of materials to optimize the structural and operational design of buildings, factories, machines, etc. is a rapidly expanding application of GAs. These are being created for such uses as optimizing the design of heat exchangers, robot gripping arms, satellite booms, building trusses, flywheels, turbines, and just about any other computerassisted engineering design application. There is work to combine GAs optimizing particular aspects of engineering problems to work together, and some of these can not only solve design problems, but also project them forward to analyze weaknesses and possible point failures in the future so these can be avoided.



Robotics Robotics involves human designers and engineers trying out all sorts of things in order to create useful machines that can do work for humans. Each robot’s design is dependent on the job or jobs it is intended to do, so there are many different designs out there. GAs can be programmed to search for a range of optimal designs and components for each specific use, or to return results for entirely new types of robots that can perform multiple tasks and have more general application. GA-designed robotics just might get us those nifty multi-purpose, learning robots we’ve been expecting any year now since we watched the Jetsons as kids, who will cook our meals, do our laundry and even clean the bathroom for us!



Evolvable Hardware Evolvable hardware applications are electronic circuits created by GA computer models that use stochastic (statistically random) operators to evolve new configurations from old ones. As the algorithm does its thing in the running model, eventually a circuit configuration will come along that does what the designer wants. Think of reconfigurable circuits in something like a space robot. It could use a built-in GA library and simulator to re-design itself after something like radiation exposure that messes up its normal configuration, or encounters a novel situation in which it needs a function it doesn’t already have. Such GAs would enable self-adaptation and self-repair. (Autonomous College Affiliated to University of Mumbai)



KJSCE/IT/LY/SEM VIII/SC/2018-19

Optimized Telecommunications Routing Do you find yourself frustrated by slow LAN performance, inconsistent internet access, a FAX machine that only sends faxes sometimes, your land line’s number of ‘ghost’ phone calls every month? Well, GAs are being developed that will allow for dynamic and anticipatory routing of circuits for telecommunications networks. These could take notice of your system’s instability and anticipate your re-routing needs. Using more than one GA circuit-search at a time, soon your interpersonal communications problems may really be all in your head rather than in your telecommunications system. Other GAs are being developed to optimize placement and routing of cell towers for best coverage and ease of switching, so your cell phone and blackberry will be thankful for GAs too.



Joke and Pun Generation Among the linguistic applications of GAs – including a JAPE (automated pun generator) inspired STANDUP program to design communications strategies for people working with children who suffer communications disabilities – are GAs that search for jokes and puns. These come under the heading of “artificial creativity” and AI, but could prove very useful to class clowns and wannabe punsters whose public reputations depend upon being funnier than they actually are. These clever GAs will let you input a word you wish to pun or a subject you’d like to joke about, and will return a variety of solutions that just might lead to a lucrative career on the comedy club circuit!



Biomimetic Invention Biomimicry or biomimetics is the development of technologies inspired by designs in nature. Since GAs are inspired by the mechanisms of biological evolution, it makes sense that they could be used in the process of invention as well. GAs rely primarily on something called implicit parallelism (like to like), using mutation and selection in secondary roles toward a design solution. GA programmers are working on applications that not only analyze the natural designs themselves for a return on how they work, but can also combine natural designs to create something entirely new that can have exciting applications.



Trip, Traffic and Shipment Routing New applications of a GA known as the “Traveling Salesman Problem” or TSP can be used to plan the most efficient routes and scheduling for travel planners, traffic routers and even shipping companies. The shortest routes for traveling. The timing to avoid traffic tie-ups and rush hours. Most efficient use of transport for shipping, even to including pickup loads and deliveries along the way. The program can be modeling all this in the background while the human agents do other things, improving productivity as well! Chances are increasing steadily that when you get that trip plan packet from the travel agency, a GA contributed more to it than the agent did.



Computer Gaming Those who spend some of their time playing computer Sims games (creating their own civilizations and evolving them) will often find themselves playing against sophisticated artificial intelligence GAs instead of against other human players online.



Encryption and Code Breaking

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

On the security front, GAs can be used both to create encryption for sensitive data as well as to break those codes. Encrypting data, protecting copyrights and breaking competitors’ codes have been important in the computer world ever since there have been computers, so the competition is intense.

(Autonomous College Affiliated to University of Mumbai)

KJSCE/IT/LY/SEM VIII/SC/2018-19

Outcomes: Understand the fundamentals of components of evolutionary computation and their applications.

Conclusion: (Conclusion to be based on outcomes) Understood the concept of Genetic algorithm and implemented the Knapsack code in R.

Grade: AA / AB / BB / BC / CC / CD /DD

Signature of faculty in-charge with date References: Books/ Journals/ Websites: 1. S.N.Sivanandam & S.N.Deepa, “Principles of Soft Computing”, Wiley India

(Autonomous College Affiliated to University of Mumbai)