Heuristic algorithms

Author: Anmol Singh (as2753) (ChemE 6800 Fall 2020)

Introduction

In mathematical programming, a heuristic algorithm is a procedure that determines near-optimal solutions to an optimization problem. However, this is achieved by trading optimality, completeness, accuracy, or precision for speed. Nevertheless, heuristics is a widely used technique for a variety of reasons:

• Problems that do not have an exact solution or for which the formulation is unknown
• The computation of a problem is computationally intensive
• Calculation of bounds on the optimal solution in branch and bound solution processes

Methodology

Optimization heuristics can be categorized into two broad classes depending on the way the solution domain is organized:

Construction methods (Greedy algorithms)

The greedy algorithm works in phases, where the algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. It is a technique used to solve the famous “traveling salesman problem” where the heuristic followed is: "At each step of the journey, visit the nearest unvisited city."

Example: Scheduling Problem

You are given a set of N schedules of lectures for a single day at a university. The schedule for a specific lecture is of the form (s time, f time) where s time represents the start time for that lecture, and similarly, the f time represents the finishing time. Given a list of N lecture schedules, we need to select a maximum set of lectures to be held out during the day such that none of the lectures overlaps with one another i.e. if lecture L_i and L_j are included in our selection then the start time of j ≥ finish time of i or vice versa. The most optimal solution to this would be to consider the earliest finishing time first. We would sort the intervals according to the increasing order of their finishing times and then start selecting intervals from the very beginning.

Local Search methods

The Local Search method follows an iterative approach where we start with some initial solution, explore the neighborhood of the current solution, and then replace the current solution with a better solution. For this method, the “traveling salesman problem” would follow the heuristic in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle.

Example Problem

Suppose that the problem P is to find an optimal ordering of N jobs in a manufacturing system. A solution to this problem can be described as an N-vector of job numbers, in which the position of each job in the vector defines the order in which the job will be processed. For example, [3, 4, 1, 6, 5, 2] is a possible ordering of 6 jobs, where job 3 is processed first, followed by job 4, then job 1, and so on, finishing with job 2. Define now M as the set of moves that produce new orderings by the swapping of any two jobs. For example, [3, 1, 4, 6, 5, 2] is obtained by swapping the positions of jobs 4 and 1.

Popular Heuristic Algorithms

Genetic Algorithm

The term Genetic Algorithm was first used by John Holland. They are designed to mimic the Darwinian theory of evolution, which states that populations of species evolve to produce more complex organisms and fitter for survival on Earth. Genetic algorithms operate on string structures, like biological structures, which are evolving in time according to the rule of survival of the fittest by using a randomized yet structured information exchange. Thus, in every generation, a new set of strings is created, using parts of the fittest members of the old set. The algorithm terminates when the satisfactory fitness level has been reached for the population or the maximum generations have been reached. The typical steps are:

1.     Choose an initial population of candidate solutions

2.     Calculate the fitness, how well the solution is, of each individual

3.     Perform crossover from the population. The operation is to randomly choose some pair of individuals like parents and exchange so parts from the parents to generate new individuals

4.     Mutation is to randomly change some individuals to create other new individuals

5.     Evaluate the fitness of the offspring

6.     Select the survive individuals

7.    Proceed from 3 if the termination criteria have not been reached

Tabu Search Algorithm

Tabu search (TS) is a heuristic algorithm created by Fred Glover using a gradient-descent search with memory techniques to avoid cycling for determining an optimal solution. It does so by forbidding or penalizing moves that take the solution, in the next iteration, to points in the solution space previously visited. The algorithm spends some memory to keep a Tabu list of forbidden moves, which are the moves of the previous iterations or moves that might be considered unwanted. A general algorithm is as follows:

1.     Select an initial solution s₀ ∈ S. Initialize the Tabu List L₀ = ∅ and select a list tabu size. Establish k = 0.

2.     Determine the neighborhood feasibility N(s_k) that excludes inferior members of the tabu list L_k.

3.     Select the next movement s_{k + 1} from N(S_k) or L_k if there is a better solution and update L_{k + 1}

4.     Stop if a condition of termination is reached, else, k = k + 1 and return to 1

Example: The Classical Vehicle Routing Problem

Vehicle Routing Problems have very important applications in distribution management and have become some of the most studied problems in the combinatorial optimization literature. These include several Tabu Search implementations that currently rank among the most effective. The Classical Vehicle Routing Problem (CVRP) is the basic variant in that class of problems. It can formally be defined as follows. Let G = (V, A) be a graph where V is the vertex set and A is the arc set. One of the vertices represents the depot at which a fleet of identical vehicles of capacity Q is based, and the other vertices customers that need to be serviced. With each customer vertex v_i are associated a demand q_i and a service time t_i. With each arc (v_i, v_j) of A are associated a cost c_ij and a travel time t_ij. The CVRP consists of finding a set of routes such that:

1.     Each route begins and ends at the depot

2.     Each customer is visited exactly once by exactly one route

3.     The total demand of the customers assigned to each route does not exceed Q

4.     The total duration of each route (including travel and service times) does not exceed a specified value L

5.     The total cost of the routes is minimized

A feasible solution for the problem thus consists of a partition of the customers into m groups, each of total demand no larger than Q, that are sequenced to yield routes (starting and ending at the depot) of duration no larger than L.

Simulated Annealing Algorithm

The Simulated Annealing Algorithm was developed by Kirkpatrick et. al. in 1983 and is based on the analogy of ideal crystals in thermodynamics. The annealing process in metallurgy can make particles arrange themselves in the position with minima potential as the temperature is slowly decreased. The Simulation Annealing algorithm mimics this mechanism and uses the objective function of an optimization problem instead of the energy of a material to arrive at a solution. A general algorithm is as follows :

1.    Fix initial temperature (T⁰)

2.    Generate starting point x⁰ (this is the best point X^* at present)

3.    Generate randomly point X^S (neighboring point)

4.    Accept X^S as X^* (currently best solution) if an acceptance criterion is met. This must be such a condition that the probability of accepting a worse point is greater than zero, particularly at higher temperatures

5.    If an equilibrium condition is satisfied, go to (6), otherwise jump back to (3).

6.    If termination conditions are not met, decrease the temperature according to a certain cooling scheme and jump back to (1). If the termination conditions are satisfied, stop calculations accepting the current best value X^* as the final (‘optimal’) solution.

Numerical Example: Knapsack Problem

One of the most common applications of the heuristic algorithm is the Knapsack Problem, in which a given set of items (each with a mass and a value) are grouped to have a maximum value while being under a certain mass limit. It uses the Greedy Approximation Algorithm to sort the items based on their value per unit mass and then includes the items with the highest value per unit mass if there is still space remaining.

Example

The following table specifies the weights and values per unit of five different products held in storage. The quantity of each product is unlimited. A plane with a weight capacity of 13 is to be used, for one trip only, to transport the products. We would like to know how many units of each product should be loaded onto the plane to maximize the value of goods shipped.

Product (i)	Weight per unit (wi)	Value per unit (vi)
1	7	9
2	5	4
3	4	3
4	3	2
5	1	0.5

Solution:

(a) Stages:

We view each type of product as a stage, so there are 5 stages. We can also add a sixth stage representing the endpoint after deciding

(b) States:

We can view the remaining capacity as states, so there are 14 states in each stage: 0,1, 2, 3, …13

(c) Possible decisions at each stage:

Suppose we are in state s in stage n (n < 6), hence there are s capacity remaining. Then the possible number of items we can pack is:

j = 0, 1, …[s/w_n]

For each such action j, we can have an arc going from the state s in stage n to the state n – j*w_n in stage n + 1. For each arc in the graph, there is a corresponding benefit j*v_n. We are trying to find a maximum benefit path from state 13 in stage 1, to stage 6.

(d) Optimization function:

Let f_n(s) be the value of the maximum benefit possible with items of type n or greater using total capacity at most s

(e) Boundary conditions:

The sixth stage should have all zeros, that is, f₆(s) = 0 for each s = 0,1, … 13

(f) Recurrence relation:

f_n(s) = max {j*v_n + f_n+1(s – j*w_n)}, j = 0, 1, …, [s/w_n]

(g) Compute:

The solution will not show all the computations steps. Instead, only a few cases are given below to illustrate the idea.

• For stage 5, f₅(s) = max_{j=0, 1, …[s/1]} {j*0.5 + 0} = 0.5s because given the all zero states in stage 6, the maximum possible value is to use up all the remaining s capacity.
• For stage 4, state 7,

f₄(7) = max_{j=0,1, …, [7/w4]} = {j*v₄ + f₅(7 - w_4*j)}

= max {0 + 3.5; 2 + 2; 4 + 0.5}

= 4.5

Using the recurrence relation above, we get the following table:

Unused Capacity s	f1(s)	Type 1 opt	f2(s)	Type 2 opt	f3(s)	Type 3 opt	f4(s)	Type 4 opt	f5(s)	Type 5 opt	f6(s)
13	13.5	1	10	2	9.5	3	8.5	4	6.5	13	0
12	13	1	9	2	9	3	8	4	6	12	0
11	12	1	8.5	2	8	2	7	3	5.5	11	0
10	11	1	8	2	7	2	6.5	3	5	10	0
9	10	1	7	1	6.5	2	6	3	4.5	9	0
8	9.5	1	6	1	6	2	5	2	4	8	0
7	9	1	5	1	5	1	4.5	2	3.5	7	0
6	4.5	0	4.5	1	4	1	4	2	3	6	0
5	4	0	4	1	3.5	1	3	1	2.5	5	0
4	3	0	3	0	3	1	2.5	1	2	4	0
3	2	0	2	0	2	0	2	1	1.5	3	0
2	1	0	1	0	1	0	1	0	1	2	0
1	0.5	0	0.5	0	0.5	0	0.5	0	0.5	1	0
0	0	0	0	0	0	0	0	0	0	0	0

Optimal solution: The maximum benefit possible is 13.5. Tracing forward to get the optimal solution: the optimal decision corresponding to the entry 13.5 for f₁(1) is 1, therefore we should pack 1 unit of type 1. After that we have 6 capacity remaining, so look at f₂(6) which is 4.5, corresponding to the optimal decision of packing 1 unit of type 2. After this, we have 6-5 = 1 capacity remaining, and f₃(1) = f₄(1) = 0, which means we are not able to pack any type 3 or type 4. Hence we go to stage 5 and find that f₅(1) = 1, so we should pack 1 unit of type 5. This gives the entire optimal solution as can be seen in the table below:

Optimal solution
Product (i)	Number of units
1	1
2	1
5	1

Applications

Heuristic algorithms have become an important technique in solving current real-world problems. Its applications can range from optimizing the power flow in modern power systems to groundwater pumping simulation models. Heuristic optimization techniques are increasingly applied in environmental engineering applications as well such as the design of a multilayer sorptive barrier system for landfill liner. Heuristic algorithms have also been applied in the fields of bioinformatics, computational biology, and systems biology.

Conclusion

Heuristic algorithms are not a panacea, but they are handy tools to be used when the use of exact methods cannot be implemented. Heuristics can provide flexible techniques to solve hard problems with the advantage of simple implementation and low computational cost. Over the years, we have seen a progression in heuristics with the development of hybrid systems that combine selected features from various types of heuristic algorithms such as tabu search, simulated annealing, and genetic or evolutionary computing. Future research will continue to expand the capabilities of existing heuristics to solve complex real-world problems.