Modeling and Analysis: Heuristic Search Methods and Simulation

Chapter 10: Modeling and Analysis: Heuristic Search Methods and Simulation Business Intelligence and Analytics: Systems for Decision Support

Learning Objectives

• Explain the basic concepts of simulation and heuristics, and when to use them

• Understand how search methods are used to solve some decision support models

• Know the concepts behind and applications of genetic algorithms

• Explain the differences among algorithms, blind search, and heuristics

• Understand the concepts and applications of different types of simulation

• Explain what is meant by system dynamics, agent-based modeling, Monte Carlo, and discrete event simulation

• Describe the key issues of model management

Problem-Solving Search Methods

• Definition of Search: The choice phase of decision-making, identifying the best possible solution or course of action under limitations such as time constraints.

• Search Techniques Include:

  • Analytical techniques

  • Algorithms

  • Blind searching

  • Heuristic searching

Types of Search Approaches

• Optimization (Analytical):

  • Generate improved solutions or obtain the best solution directly.

  • Stop when no improvement is possible.

• Complete Enumeration (Exhaustive):

  • All possible solutions are checked.

  • Stop when all alternatives are checked (optimal).

• Partial Search:

  • Check only some alternatives systematically dropping inferior solutions (best among checked).

• Heuristics:

  • Only promising solutions are considered; stop when a solution is good enough (good enough).

Algorithmic/Heuristic Search Methods

• Benefits of Heuristics:

  • Cuts the search space.

  • Obtains satisfactory solutions more quickly and at a lower cost.

  • Finds good-enough feasible solutions to complex problems.

• Types of Heuristics:

  • Quantitative

  • Qualitative

Example: Traveling Salesman Problem

• Definition: A traveling salesman must visit multiple cities, visiting each only once. The goal is to find the shortest possible route.

• Total Number of Unique Routes (TNUR): $TNUR = (1/2) imes (Number \, of \, Cities - 1)! imes Number \, of \, Cities$

  • For example:

  • For 5 cities: TNUR = 12

  • For 6 cities: TNUR = 60

  • For 9 cities: TNUR = 20,160

  • For 20 cities: TNUR ≈ 1.22 imes 10^{18}

Cities and Distances Example

Heuristic Rules for TSP

• Rule 1: Starting from home base, go to the closest city.

• Rule 2: Always follow an exterior route.

• Example Route Efficiency:

  • Using Rule 1 leads to a distance of 7,580 miles.

  • Using Rule 2 leads to a distance of 7,005 miles.

When to Use Heuristics

• Use Heuristics When:

  • Inexact or limited input data is available.

  • The reality is complex.

  • Reliable, exact algorithms are not available.

  • Computation time is excessive.

  • Quick decision-making is necessary.

• Limitations of Heuristics:

  • Cannot guarantee an optimal solution.

Modern Heuristic Methods

• Examples Include:

  • Tabu search: Intelligent search that avoids cycles.

  • Genetic algorithms: Mimicking natural evolution processes.

  • Simulated annealing: Analogy to thermodynamics, exploring solution spaces.

  • Ant colony optimization: Mimicking how ants find paths.

Genetic Algorithms

• Definition: A popular heuristic search technique that mimics the biological process of evolution to find optimal solutions across various domains.

• Key Themes:

  • "Survival of the fittest," gradually improving solutions by allowing only the fit parents to create successive generations.

  • Each candidate solution is termed a chromosome, represented as a string of genes.

  • Chromosome Features:

  • Can copy, mate, and mutate.

GA Structure and Operators

• Genetic Operators:

  • Reproduction: Creating copies of chromosomes.

  • Crossover: Combining parts of parent chromosomes to produce offspring.

  • Mutation: Randomly altering genes to maintain genetic diversity.

Example: The Knapsack Problem

• Problem Definition: Fill a knapsack to maximize benefit without exceeding a weight limit (22 pounds).

• Item Specification:

  Item No	Benefit	Weight
  1	5	7
  2	8	3
  …	…	…

• Chromosome Representation:

  • Example Solution: 1100001 means select items 1, 2, and 5.

• Optimal Checks lie in balancing weight against benefits to maximize the utility of the knapsack.

Limitations of Genetic Algorithms

• Challenges:

  • Doesn't guarantee optimal solutions, may converge at local minima.

  • Not all problems are formulable for GA.

  • Requires programming and statistical skills—heavy reliance on random number generators.

  • Locating good variables and obtaining required data is complex.

Applications of Genetic Algorithms

• Use Cases in Various Fields:

  • Dynamic process control

  • Optimization of rules in systems

  • New topologies in connectivity

  • Simulation of biological models of behavior

  • Advanced engineering design

  • Pattern recognition, scheduling, routing, circuitry design.

Simulation

• Definition: Simulation refers to creating an appearance of reality to perform what-if analysis on a system model, extending beyond typical decision support techniques due to system complexity.

• Characteristics of Simulation:

  • Alike in shape and behavior to actual systems.

  • Acts as a technique for conducting experiments, descriptive in nature.

  • Best employed when numerical optimization isn't feasible.

Advantages of Simulation

• Straightforward theoretical foundation.

• Allows for time compression in tests.

• Experiments with diverse alternatives are feasible.

• Models reflect managerial perspectives and complexities.

• Generates crucial performance metrics and insights.

• Often the sole modeling tool for non-structured problems.

Disadvantages of Simulation

• Cannot ensure optimal solutions.

• Slow and costly to produce models.

• Difficulty in transferring solutions to different problems.

• Can overemphasize simulation benefits, possibly sidelining analytical solutions.

• Software may require specialized skills.

Simulation Methodology Steps

1. Define the problem.

2. Construct the model.

3. Test and validate the model.

4. Design experiments.

5. Conduct experiments.

6. Evaluate results.

7. Implement solution.

Types of Simulation

• Probabilistic/Stochastic vs. Deterministic Simulation

  • Stochastic incorporates probability distributions.

• Time-Dependent vs. Time-Independent Simulation

  • Example: Monte Carlo technique involves time variables.

• Discrete Event vs. Continuous Simulation

• Visual Interactive Simulation (VIS): Graphical interface for modeling; allows dynamic adjustments and sensitivity analysis.

System Dynamics Modeling

• Overview: Encompasses macro-level aggregate trends and behaviors over time, focusing on system interactions.

• Initially proposed by Jay Forrester in 1958, it's prevalent in operations research.

Agent-Based Modeling (ABM)

• Agents are autonomous programs interacting and achieving specific goals in simulated environments.

• Characteristics:

  • Discernible from other modeling approaches through a bottom-up perspective.

  • Platforms include SWARM, Netlogo, and RePast/Sugarscape.

Conclusion

• End of Chapter: Discussions on heuristic search methods and simulation emphasize their critical roles in decision support systems, particularly in the face of complex systems requiring both innovative solutions and data-driven analyses.