Evolutionary Algorithms Quiz

Optimization Methods

• Exact methods find optimal solutions, guaranteeing optimality.
• For NP-complete problems, exact algorithms take non-polynomial time.
• Approximate methods generate high-quality solutions in a reasonable time, but don't guarantee optimality.

Heuristics

• Heuristics are approximate algorithms that aim to find good solutions quickly.
• The word "heuristic" comes from the Greek word "heuriskein," meaning "to discover."
• Heuristics generate practical solutions in a reasonable time.

Metaheuristics

• Metaheuristics are high-level strategies that guide the design and application of heuristics.
• They are general methodologies applied to specific optimization problems.
• They guide the design of heuristics to solve particular optimization problems.

Genealogy of Metaheuristics

• A diagram illustrating the development of metaheuristic algorithms over time.
• Different metaheuristic algorithms are connected by lines, to show the lineage relationship.
• It visually depicts the evolutionary development.

Exploitation vs. Exploration

• Metaheuristics use exploitation to intensify the search around promising regions.
• Metaheuristics use exploration to diversify the search to discover new areas of the solution space.
• Both exploration and exploitation are necessary for effective search in complex problem spaces.

Metaheuristics Classifications

• Metaheuristics can be categorized based on population size.
• Trajectory-based algorithms (e.g., hill climbing, tabu search) operate on a single solution.
• Population-based algorithms (e.g., genetic algorithms, PSO) maintain a population of solutions.

Classification Criteria

• Nature-inspired vs. non-nature-inspired methods
• Single-solution vs. population-based methods
• Deterministic vs. stochastic methods
• Iterative vs. greedy methods

Greedy Heuristics

• Greedy heuristics make locally optimal choices at each step.
• The process of constructing a solution through specific steps.
• Making optimal decisions at each step does not guarantee a global optimum.

Greedy Heuristics for TSP

• Nearest Neighbor Algorithm. Selecting a node randomly to start a path and connect to the nearest unvisited node. Repeating until all nodes are covered.
• Complexity is O(n²).
• Shows a step-by-step process for constructing a path/solution.

TSP Example

• Traveling Salesman Problem (TSP) is a classical optimization problem needing to find the shortest tour through a given set of cities.
• All cities must be visited exactly once.
• The aim is to minimise the total distance.

When to Use Metaheuristics

• Easy (P class) problems with very large problem instances.
• Easy problems with stringent (tight) real-time constraints.
• Difficult optimization problems with moderate instances or complex input structures.
• Optimization with time-consuming objectives or constraints.
• Non-analytical models (black-box) of optimization problems.
• Non-deterministic or complex problem models (e.g., uncertainty, robust optimization, dynamic, multi-objective).

Common Design Concepts for Iterative Metaheuristics

• Representation (Encoding) as the search space.
• Objective function that represents the optimization goal.
• Search space and objective function collectively define the search space "landscape."

Representation Characteristics

• Completeness: All possible solutions must be represented.
• Connexity: A path must exist between any two solutions, especially to the global optimum.
• Efficiency: the representation allows manipulation by search operators with acceptable time and space complexity.

Types of Representations

• Linear representation (e.g., strings of symbols, binary encoding).
• Vector of discrete or real values (e.g., location problems, parameter identification, scheduling problems).
• Permutation (e.g., traveling salesman problem).
• Non-linear representation (e.g., graphs, trees).

Objective Function

• The objective function defines the problem's goal. It assigns a numerical value to each solution, representing its quality.
• An absolute value that defines the complete ordering of all solutions in the search space.

Self-Sufficient Objective Functions

• Form of objective functions representing the original problem formulation.
• TSP: total distance minimization.
• SAT: Boolean formula satisfaction.
• NLP (non-linear programs): minimizing a function.

Guiding Objective Functions

• Transforming the original optimization goal to improve the algorithm’s convergence (guiding the search).
• SAT example to illustrate: Non-optimal solutions receive a ‘false’ value.

Constraint Handling

• Reject strategies: discard infeasible solutions.
• Penalizing strategies: penalize infeasible solutions using penalty function.
• Repairing strategies: repair infeasible solutions.
• Decoding strategies: generate only feasible solutions.
• Preserving strategies: maintain feasibility through operators.

Parameter Tuning and Performance Analysis

• Parameter tuning (HPO)
• Experiment design: goals, instances, and defining factors.
• Measurement: compute measures and perform statistical analysis.
• Reporting: comprehensive and reproducible reports.

Quality of Solutions for Measurement

• Global optimal solution: obtained using exact algorithms or constructed.
• Bounds: from relaxation methods
• Best known solution: standard libraries providing the best known solutions
• Requirements: Solution quality requirement defined by decision maker.

Statistical Analysis for Measurement

• Kolmogorov-Smirnov or other tests for normality.
• Parametric tests (t-test; ANOVA) or non-parametric tests (Wilcoxon, sign, permutation tests).

Reporting: Interaction Plots

• Interaction plots visualise the effect of two factors (parameters) on results.
• Visualise the trade-off between different performance indicators (e.g., quality, search time, robustness).

Single-solution Based Metaheuristics

• Focuses on improving a single solution iteratively by exploring the neighborhood using intensification.
• This means exploring the immediate neighbourhood repeatedly in the search space.

Single Solution Based Metaheuristics (Algorithm)

• Algorithm template for a Single-Solution metaheuristic.
• Input: initial solution.
• Iterative Steps: generate, select, update the best solution.
• Output: best solution found (that meets the stopping criteria).

Common Concepts for S-metaheuristics

• Basic concepts of Neighborhoods, including defining strong and weak locality.
• Definitions of neighborhoods in discrete and continuous solution spaces
• Characterization of Neighborhoods for permutation problems like TSP

Local Optimum

• A local optimum is a solution that is better than its neighbors (according to the objective function).
• It might not be the absolute best in the entire search space.

Initial Solution for S-metaheuristics

• Initial solutions can be random or use heuristics
• Trade-off between quality and computational time with these choices

Local Search Method

• A step-by-step explanation of a local search algorithm.
• Includes identifying initial solutions, intensification moves, and diversification operators (perturbation)
• Local search operator example: 2-Opt swap, Insertion/Relocate, Reversion.
• Acceptance policy for accepting non-improving moves.

Iterated Local Search (ILS)

• High-level template for the ILS algorithm.
• Components include perturbation, local search, acceptance, stopping criteria

Extra Resources: Symmetric TSP

• The size of the search space for symmetric TSP problems is reduced.
• Formula: (n − 1)!/2.

Population-Based Algorithms

• Algorithms maintaining a population of solutions during the search process.
• Core strategy: Generate, select, reproduce, and replace solutions in the population.

Evolutionary Algorithms Framework

• Algorithm template for Evolutionary algorithms.
• Key steps include initial population generation, evaluation, selection, reproduction, and replacement, terminating based on criteria
• Illustrates the population-based approach.

Swarm Intelligence Definition

• Collective intelligence system without central coordination.
• System using simple elements (or individuals) in the decision space, communicating indirectly.

Ant Colonies

• Algorithm template for the Ant Colony Optimization (ACO) algorithm.
• Explains the core components of the algorithm: pheromone trails, solution construction, and pheromone update (evaporation and reinforcement).

Particle Swarm Optimization (PSO)

• Algorithm template for the PSO algorithm:
• Particles represented by position and velocity in the decision space.
• The method has updated velocities and positions for each particle.
• The method also updates the best positions known by each particle and the best overall.

Reproduction in Evolutionary Algorithms

• Mutation modifies the representation of individual (modifies the solution).
• Crossover combines representations of two or more individuals to create new solutions.
• Parameters like ergodicity, locality, and valid representation impact choices.

Replacement in Evolutionary Algorithms

• Generational replacement: The new population completely replaces the old one.
• Steady-state replacement: Select one parent (or a few) and one offspring to be kept in the new population.
• Elitism and the inclusion of the best solution found so far may help to maintain high-quality solutions.

Evolutionary Algorithms (General)

• Process involves evolution, reproduction, and selection of solutions across multiple iterations.

Advantages of Metaheuristics

• Wide applicability, with little presumptions about the solution space.
• Low development and implementation costs.
• The simplicity allows easy hybridization/combination with other methods.
• Offers numerous potential solutions for problems with many local optima
• Robustness to changes in the environment.

Disadvantages of Metaheuristics

• No guarantee of finding an optimal solution within a predefined time.
• May require parameter tuning for optimal performance.
• Relatively slow (particularly when fitness evaluations are complex)

Important Considerations when using Evolutionary Algorithms

• Stochastic nature means individual runs may produce different results.
• Suitable for comparisons and robust solutions.
• Properly choose objective function.
• Offspring solutions should have a chance to outperform their parents.

Common Concepts for S-Metaheuristics - Initial Solutions

• Include strategies for setting an initial solution
• Include a tradeoff between quality and computational time

Local Search - Method (History of Hikers)

• Illustrates the concept of local search, showing how different approaches to searching may lead to local rather than global solutions.
• Proposes different strategies (Enumeration, Greedy...) to explore different neighborhoods and escape from local optima.
• Proposes different strategies for improving local search methods.

Exercises

• Small exercises to illustrate how a crossover or other operators work on two given solutions to find offspring solutions.
• Illustrate different representations and how those can be applied to given problems.

Additional Considerations

• Further exploration of factors that can influence choosing the suitable metaheuristic algorithm for a specific problem.