7. Metaheuristic Multi-Objective Optimizaiton

Eugenics babyyyy

Slides: 7 - Metaheuristic Multi-Objective Optimizaiton.pdf

---

Genetic algorithms

• Inspired by natural selection / survival of the fittest
• Population of individuals (potential solutions) instead of single solutions (metaheuristic search is performed in a parallel manner)
• Algorithm provides a set of improved solutions at each generation (iteration)

• Each individual or chromosome represents a potential solution vector of decision variables
• These chromosomes contain discrete unit called genes, for the decision variables

Encoding

These decision variables need to be encoded in some way. In GIS there are three common encodings (for e.g. locations):

• Binary representation
• Discrete representation: assigning a score
• Order (or permutation) based representation

The choice of encoding strategy is problem dependent.

Initialization

• Quality of results depends on size of the initial population and the way it is constructed
• The main consideration in the process is diversification: making sure that there are enough differing chromosomes out there to explore different solutions
• If the population is not well diversified, a premature convergence (a convergence toward a suboptimal result or local optimum) can occur

Common methods for initialization:

• Random generation
• Sequential diversification
• Parallel diversification
• Heuristics

Evaluation

• Assign a fitness value to measure the quality of each solution
• In general, the techniques for fitness assignment are based on the concepts and methods of the conventional multiobjective optimization procedures: example: weighted-sum approach
• The weighted-sum approach transforms the multicriteria decision problem into a single criterion one.

Selection

• Survival-of-the-fittest principle to choose “high quality” individuals (solutions) from the current population
• At each successive generation: the higher the fitness of the individual, the higher the probability of it being selected into a mating pool (temporary population)

Crossover

Chromosomes are recombined to make new offspring. For each index, we could pick the gene from either parent. There are 3 common ways to do this:

Mutation

• Another way of ensuring diversification
• Mutation occurs on a single solution (offspring)
• Altering one or more gene values of individuals to create new solutions

Simulated Annealing (SA)

Simulated annealing - Wikipedia

Mimics the process of arranging atoms when a material (steel or glass) is heated and then slowly cooled.

During the process of crystallization, the temperature controls the arrangement of atoms in their lowest-energy configuration. Eventually, when the material approaches zero temperature, the atoms approach their minimum energy state.

TLDR

A process where we always accept a better option, and have a chance of accepting a worse solution in the hopes of escaping a local minimum. This chance decreases over time, and the solution starts to stabilize.

• The goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.
• Generates moves randomly in the solution space searching for a solution that minimizes the value of an objective function.
• The algorithm always accepts moves that decrease the value of the objective function.
• However, changes that increase the value of the objective function are accepted with a small probability that depends on a control parameter called the temperature.

The probability of accepting a worse point: $\exp (\Delta \frac{E}{T})$

So with a higher temperature, we have a higher chance of accepting worse value.

Analogy

Climbing mountains to find the lowest point. In the beginning we have more energy and are willing to take more risk, but after a while we get tired and stop climbing up.

Swarm Intelligence

Inspired by social behaviors in swarm animals. A swarm is a self-organized, multi-agent system in which the individuals (agents) cooperate to accomplish complex tasks, without any centralized control.

• The global pattern of agents emerges from local interactions between agents, which occur through direct (agent-to-agent) or indirect (via the environment) communication.
• Each agent follows a set of rules influenced by locally available information

Ant Colony Optimization (ACO)

A self-organizing system of ants, each acting as their own agent

Ants leave pheromones behind, attracting other ants.

• Ants form and maintain a line to their food source by laying a trail of pheromones.

• They deposit a certain amount of pheromone while walking, and each ant prefers to follow a direction marked by high concentration of pheromone.

• This enables the colony of ants to quickly find the shortest route

• At the beginning of the searching process, the ants explore all the paths or routes

• Gradually the shortest path is marked with more pheromone than other routes because the self-regulating mechanism attracts more and more ants to the route characterized the highest level of pheromone.

• Sooner or later, nearly all the ants are choosing the shortest path.

Probability of taking a route between node $i$ and $j$:

To diversify we can:

• Let pheromones evaporate (reduce) over time
• Increase the pheromone values for good solutions while decreasing the pheromones for bad solutions

Particle Swarm Optimization (PSO)

Inspired by flocks of birds, fish, etc.

An individual/agent is referred to as a particle, and behaves according to a combination of their own intelligence and the collective intelligence of the population.

• Each particle has its own velocity and position (location) in a multi- dimensional search space
• The particles move through the space seeking a good solution
• The particles communicate their current locations to neighboring particles.
• The position of each particle is adjusted according to its velocity (i.e., rate of change) and the difference between its current position and the best position found by its neighbors, and the best position it has found so far

Velocity is defined by three elements:

• Inertia based on the current velocity value of the element
• Personal influence based on the solution element of the particle’s own best solution so far (called local best)
• Social influence based on the solution element of the best particle found in the population during the search process (called global best)