Манiло В.В. APPLYING GENETIC ALGORITHMS TO FORMIG SCHEDULE

Манiло Володимир Володимирович / Manilo Volodymyr Volodymyrovych

НТУУ «КПI» / NTUU "KPI"

APPLYING GENETIC ALGORITHMS TO FORMIG SCHEDULE

Genetic algorithms (GAs) are numerical optimization algorithms inspired by both natural selection and natural genetics. The method is  a general one, capable of being applied to an extremely wide range of problems. Unlike some approaches, their promise has rarely been over-sold and they are being used to help solve practical problems on a daily basis. The algorithms are simple to understand and the required computer code easy to write.[1] So, the main idea of this algorithms was taken from nature: key words "crossover"  and "mutation" are what we can observe how propagate different kind of microorganisms. Before that your embryo was formed, two cells from your mother's and father's organisms had met together and they brought a half-collection of DNA from each organisms, and then this collections mixed in some way and from this new cell you have grown up. So the DNA of new organism is a combination in  some random way from patent's collection of chromosomes. As you know, from lessons of biology, each chromosome control some parameter in our body, it can be anything: color of eyes, color of hair, height, age of living, some character traits and so on. The same mechanism was lain in this genetic algorithms, and as you have already noticed their name also come from genetics. The father of genetic algorithms is well known John Henry Holland. He started develop this idea and tried to apply it for solving different type of problems. Holland also the author of  "Adaptation in Natural and Artificial Systems"(1975), it was the first step in learning GAs. Now a bit about mutation - it's one of the most familiar of the genetic operations, its role in adaptation is frequently misinterpreted. In genetics mutation is a process where in one allele of a gene is randomly replaced by (or modified to) another to yield a new structure. Generally there is a small probability of mutation at each gene in the structure. In the formal framework this means, each structure A = a₁a₂...a_n in the population B(t), is operated upon as follows:

•1.     The positions x₁, x₂, ..., x_n to undergo mutation are determined (by a random

process where each position has a small probability of undergoing mutation,

independently of what happens at other positions).

•2.     A new structure A^' = a₁ ... a_x1-1a^'_x1a_x1+1... a_x2-1a^'_x2a_x2+1...a_n is formed where a^'_x1 is drawn at random from the range V_i of detector δ_i corresponding to position x₁, each element in V_i being an equilikely candidate: a^'_x1...,a^'_xn are determined in the same way.[2]

So a typical algorithm might consist of the following:

•1.     Start with a randomly generated population of n l-bit chromosomes (candidate solutions to a problem).

•2.     Calculate the fitness ƒ(x) of each chromosome x in the population.

•3.     Repeat the following steps until n offspring have been created:

•a.      Select a pair of parent chromosomes from the current population, the probability of selection being an increasing function of fitness. Selection is done "with replacement," meaning that the same chromosome can be selected more than once to become a parent.

•b.     With probability pc (the "crossover probability" or "crossover rate"), cross over the pair at a randomly chosen point (chosen with uniform probability) to form two offspring. If no crossover takes place, form two offspring that are exact copies of their respective parents. (Note that here the crossover rate is defined to be the probability that two parents will crossover in a single point. There are also "multi-point crossover" versions of the GA in which the crossover rate for a pair of parents is the number of points at which a crossover takes place.)

•c.     Mutate the two offspring at each locus with probability pm (the mutation probability or mutation rate), and place the resulting chromosomes in the new population.

If n is odd, one new population member can be discarded at random.

•4.     Replace the current population with the new population.

•5.     Go to step 2.[3]

Fitness function it's one of the key point in GAs, it's estimate how much possibilities to live has each chromosomes, and it is formed individual for each problem.

So for solving my problem which connected with forming school schedule, I did the following: I made a structure of lesson with such fields as (teacher, time from-till, group which has a lesson, room, day) and this structure represents the only one "gene" in my chromosome, and the total schedule for a week - it's the main chromosome. I wrote this program on Java, and using OO's concepts help to achieve good level of abstraction. So, for working with chromosomes I used LinkedList collection with my class Lesson, which represented genes in my chromosome. And then for stored the whole population I used also LinkedList, but each element of this collection was chromosome, that I mentioned above. My fitness function calculate how much lessons overlay in the same time, same place, or using one teacher in different places at the same time and so on, and then I got a coefficient, which shows me how closely I've approached to the goal. At first I generate population of 50 "individuals", and then make crossover within this population, each pair gives me 3 new individuals, then I re-estimate all individuals and sort the list all individuals, and then form new population from the top 50 of sorted list. And then loop continue for several times, nearby 150 times. And that's more effective then tries to solve this problem by "brute-force" - making all possible variants and then choose the best one.

Before generating first population I know about all teachers, rooms, groups that I have, so I have limitation on amount of room, teacher, max teacher's work hours per week, max lessons per a day.

Literature

•1.   David A. Coley, 1997, An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific

•2.   John H. Holland, 1992, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The MIT Press

•3.   Mitchell M., 1999, An introduction to genetic algorithms, The MIT Press

e-mail: wmanilo@gmail.com

Залиште коментар!