SA Questions

1.    SA always accepts transitions that improve the solution.

a)    True

b)    False

2.    The likelihood with which SA accepts solution-worsening transitions depends on the temperature, the magnitude of the change in energy, and the solution where it currently is at.

a)    True

b)    False

3.    Steepest descent behaves no differently than simulated annealing at zero temperature.

a)    True

b)    False

4.    SA does not give the same results in Miami as in Anchorage because of the difference in temperature between the two cities.

a)    True

b)    False

5.    SA accepts more transitions at higher temperatures.

a)    True

b)    False

6.    Solutions from SA can be worse than those from steepest descent.

a)    True

b)    False

7.    SA has to follow a slow cooling-off schedule to ensure the quality of the solution.

a)    True

b)    False

8.    Initial conditions are immaterial for SA. Indeed, SA will come by great solutions irrespective of the starting point.

a)    True

b)    False

9.    One needs to jump in and stop SA after a certain number of iterations. Otherwise, SA may stray away from the optimal solution.

a)    True

b)    False

10. SA may not ascertain it found the optimal solution.

a)    True

b)    False

11. Endowing SA with memory (say, by keeping track of the top X solutions encountered) amounts to exploring the solution space more efficiently.

a)    True

b)    False

12. In SA, there are two probabilities: one is involved in defining the candidate solution to be evaluated (left or right transitions in the Bayser SA tool), and the other in establishing the acceptance threshold against which the candidate solution is measured. Both probabilities are related to the temperature.

a)    True

b)    False

13. What helps SA get out of local minima?

a)    The acceptance threshold is established probabilistically.

b)    The exponential form of the Metropolis condition, i.e., that p is less than exp (-DE/kT) where DE is the change in energy, T the temperature, and k is a constant.

c)     Annealing follows a declining temperature schedule.

d)    Positive energy changes are not discarded automatically.

14. What contributes to the quality of the solutions in SA?

a)    Temperature schedule.

b)    Randomness of the search.

c)     Initial conditions.

d)    All of the above.

15. How does the Objective Function impact the SA process?

a)    SA breaks down for very discontinuous objective functions.

b)    SA can only work if the objective function admits multiple minima.

c)     SA requires that the Objective function be convex.

d)    SA only works for continuous Objective Functions.

16. Dart-throwing consists of randomly picking a candidate from the solution space. That candidate is accepted if it is the best solution found. In the light of this definition, what is the most fundamental difference between SA and dart-throwing?

a)    SA uses two probabilities while dart-throwing uses just one.

b)    SA uses a temperature, dart-throwing does not.

c)     The acceptance criterion for SA is probabilistic, that of dart-throwing deterministic.

d)    SA explores the solution space in the vicinity of the current solution, dart-throwing can go anywhere.

17. SA needs to remember the best solutions it comes across if a rising temperature schedule is followed. This is because:

a)    The probability of accepting any transition is increasing.

b)    SA may get further from the optimal solution as the process unfolds.

c)     SA will behave more and more like dart-throwing.

d)     All of the above.

18. Can dart throwing somehow be used to improve SA?

a)    Dart throwing and SA are two different techniques and have nothing to do with each other.

b)    SA has a small bandwidth and dart-throwing a large one. Just like we use the viewer of a telescope to zero in on the celestial object of interest before observing the object in the eyepiece, we can first use dart-throwing to identify a promising region of the solution space, then use SA to zoom in that region.

c)     Dart throwing provides better initial solutions than SA. Therefore, SA can start off with solutions generated by dart throwing, hence the gain in efficiency.

d)    Alternate between dart-throwing and SA to improve “finding power”. Indeed, dart-throwing will allow SA to get out of deep local minima.

19. Territory alignment consists of carving out geographies for members of the sales organization. One of the key objectives is that the workload be balanced. How would you deploy SA to automate territory alignment?

20. Parallel processing is a very powerful technique to cut down on execution time. How would you modify the SA framework to take advantage of parallel processing?

21. The fact that the left and right transitions in the Bayser SA tool are generated with the same probability, namely 50%, suggests that, all things being equal, the algorithm will end up where it started. What if some asymmetry were introduced, for instance 40% for the left transition and 60% for the right transition? What about running two copies of SA, one with 60-40 and the other with 40-60?

22. Endowing memory to SA may be taken to mean keeping track of the top X solutions. What are the implications of such an addition on the performance of SA?

GA Questions

1. All representations of the objective function need to be written

in the binary ‘1/0’ format.

a)    True

b)    False

2. The only operators available in creating a new generation are Crossover, Mirror, and Mutation.

a)    True

b)    False

3. If there is only one strain in the current population, we can introduce new strains in the next generation by using Crossover as the only gene operator.

a)    True

b)    False

4. The assignment of 60% Crossover, 30% Mirror, and 10% Mutation is considered a good distribution of gene operators.

a)    True

b)    False

5. Using a Genetic Algorithm guarantees you will find a very good solution in a reasonable amount of time.

a)    True

b)    False

6. A Genetic Algorithm will work best if there are a variety of strains in the initial population.

a)    True

b)    False

7. It is always better to use large populations/fewer generations than small populations/more generations when searching for the best solution.

a)    True

b)    False

8. Once a strain disappears from the population it can never reappear in the population again.

a)    True

b)    False

9. A Genetic Algorithm will find the optimal solution given the correct mix of operators and enough time.

a)    True

b)    False

10. The same solution to a problem may be arrived at in a different number of generations.

a)    True

b)    False

11. Mutating a strain is:

a)    Changing all the genes in the strain.

b)    Removing one gene in the strain.

c)     Randomly changing one gene in the strain.

d)    Removing the strain from the population.

12. Genetic Algorithms are considered pseudo-random because they:

a)    Search the solution space in a random fashion.

b)    Search the solution space using the previous generation as a starting point.

c)     Have no knowledge of what strains are contained in the next generation.

d)    Use random numbers.

13. The three gene operators we have discussed can be thought of as:

a)    Crossover: Receiving the best genes from both parents.

b)    Mutation: Changing one gene so that the child is almost like the parent.

c)     Mirror: Changing a string of genes in the child so it is like a ‘cousin’ to the parent.

d)    A and B only

e)    All of the above

14. If a population contains only one strain, you can introduce new strains by:

a)    Using the Crossover operator.

b)    Injecting random strains into the population.

c)     Using the Mutation operator.

d)    B only

e)    B and C only

15. The efficiency of a Genetic Algorithm (how quickly it arrives at the best solution) is dependent upon:

a)    The initial conditions.

b)    The size of the population.

c)     The types of operators employed.

d)    All of the above

16. Which of the following differences between Simulated Annealing and Genetic Algorithm are fundamental?

a)    There is an implicit parallelism in GA, none in SA.

b)    In SA, each solution is generated from the current solution (move right or left in the Bayser SA tool). In GA, a solution can be generated by crossing two parents (crossover operation).

c)     In SA, a candidate solution always lies in the vicinity of the current solution. In GA, the candidate solutions may be far from the current solutions.

d)    All of the above.

17. If two successive generations are identical then the Genetic Algorithm has found the optimal solution. Discuss why this statement is NOT true.

18. Are Genetic Algorithms useful if we don’t have a full understanding of our objective function?

19. Genetic Algorithms are predicated on the fact that the path to a good solution is based on having good intermediary solutions. How will the Genetic Algorithm act if there are discontinuities in the solution space?

20. Say we want to model the behavior of a foxes-and-hares eco-system. How would you extend the GA model to capture the equilibrium among different strains, i.e., the food chain equilibrium between foxes and hares?

21. How might one use Genetic Algorithms in forecasting models?

22. Link the idea of temperature in Simulated Annealing to the intensity (number of genes) and frequency (how often) of mutation in Genetic Algorithms.

23. What are the pros and cons of SA and GA? Can you conceive of a framework that combines the best of both worlds.