Opti what?

• Optimisation or Operations research

What for?

• To find the best or optimal answer to a well-defined problem

Best?

• The answer is considered optimal (out of all possible solutions to the problem) according to well-defined criterion

What did u say?

• The optimal answer serves the best under the user's objective(s)
• For examples: If u r buying bread,

1. Price - buy the cheapest
2. Quality - buy the freshest & tastiest
3. Nutrient - buy the one choke full of nuts & bolts
4. Availability - buy the one sold nearest to u

What if I want all when I buy bread?

• Simple, just find one that satisfies all those criteria
• Criteria / criterion: Objective function set

If more than 1 bread satisfies?

2 ways:

• There are now optimal answers
• You can further limit your search down to only 1 answer by imposing more objective(s)

If none satisfies?

3 ways:

• The area you search or the domain is too narrow, try widening
• You are just too picky, your Objective function set is too restrictive
• You may have missed out some good answers, try improving your search technique

Hmmm…if my area is fixed & I know exactly what I want…then how best to search?

• Good question
• There are 2 radically different ways:

1. "carpet bombing": go to every shop in your area and find the bread you want
2. "selective searching": well…select a few shops…select a few brands of bread…compare & choose

Every Tom, Dick & Harry knows carpet bombing…but selective searching?

• Are you having doubts about its reliability?
• Not always able to give the best answer?

Yap!

• This is precisely a problem (how to always find the best answer without carpet bombing) that confronts & still puzzles experts
• Not to say you & me

R we stuck or what?

• You see…the technique that you use to find the best bread is significant
• You may get a good bread or a not-so-good one depending how you go about searching

Any ideas?

• Optimisation techniques may be split into the following categories:

1. Direct searches (gradient, pattern, integer, etc.)
2. Indirect searches (random, stochastic, etc.)
3. Nature-inspired searches

What nature-inspired?

• These searches model themselves after natural phenomena like evolution, chemical changes and even brain activity

U mean if e sun goes from east to west…then I should search by going east to west?

• Ha…the answer is maybe
• You must somehow be able to justify the reliability of your search technique

Well…give some reliable natural searches

• A lot of research activities are concentrated on the following nature-inspired searches:

1. Simulated annealing
2. Neural network
3. Fuzzy logic
4. Case-based reasoning
5. Evolutionary strategies & algorithms

Evolutionary…u mean like Charles Darwin's theory?

• Exactly
• Evolutionary searches evolves their answers through many cycles, producing good if not better answers in each cycle
• The underlying principle is the survival of the fittest

What algorithms?

• Algorithms are simply the outline and concepts associated with the search
• In evolutionary algorithms, GA is the most popular & the most efficient

What's GA?

• GA stands for genetic algorithms
• It is in fact a type of computational evolution for the best, evaluated answer

Why efficient?

• Efficient in that GA is able to search through small & large domains with various objective function set with relative ease & less resources
• Other techniques like direct searches perform excellently in small domains and few objectives, but poorly in large domains, many objectives with many close answers

Wow…how's GA like?

• The main GA processes are as follows:

1. Initial population (solutions set) made up of chromosomes (possible solutions or answers
2. The Fitness of each chromosome is evaluated as a numeric value representing its suitability for survival in the problem environment
3. Parent chromosomes are selected from this population according to their fitness values (objective function set values)
4. Crossover of the parent chromosomes are carried out, just as in real-life the exchange of X & Y chromosomes from the parents
5. Mutation of the newly-formed chromosomes may be carried out to escape from a local optima, just like genetic mutation in real-life
6. The newly-crossovered & mutated population replaces the old population, just like our parents surviving our grandparents
7. The process repeats itself with hopefully population of better chromosomes with higher fitness

Man…sounds complicated…but seems not too difficult to understand

• Yes, it is modeled after nature

Where can I know more about GA?

• Here are a few websites full of GA, have fun:

1. Genetic Algorithms
2. GA Classroom
3. GA History
4. Evolutionary Research