Perform Algorithm Analysis
More complex and powerful forms of heuristics such as Memetic Algorithms, Hyper-Heuristics, etc. are usually concerned with controlling and managing a set of low-level heuristics (usually in the form of local search or refinement procedure) during runtime. Using the language of memetic computing, we refer to those low-level heuristics as meme. Adaptive and intelligent meta-heuristic algorithms such as Adaptive MA and Hyper-Heuristics adjust the selection, frequency and intensity of applied memes during the search so that parameters and operators of its algorithmic structure is auto-configured and adapt to the problem instance being solved as well as to the different search stages and fitness space neighbourhood structure.
It is important to researchers working on vehicle routing algorithms to understand the behaviour of these algorithms during runtime. For example, how much and frequent a particular meme is selected and how long it is run during which stage of search. However, most tools and frameworks currently for vehicle routing schedulers do not provide such an insight to researchers on what goes under the algorithm progress during runtime. The Vehicle Routing Scheduler Library had been built with these in mind, and provides analytics and visualization tools to study the runtime behaviours of algorithms.
- Double-click SIM solution method in Schedulers tab.
- Double-click A-n69-k9 problem instance in Benchmarks tab.
- Take note of the caption title: CVRP: Instances(A-n69-k9)(SIM)
- Go to Algorithm Analysis tab to access to algorithmic analytics and visualization tool.
- Click Run Algorithm Analysis button to start the analysis as shown in Figure.
- Results of SIM algorithm analysis are presented in frequency analysis stacked chart with a set of memes in the meme pool as shown in Figure. Initially all memes in the meme pool of SIM are given equal opportunity to run. But as the search progress, two memes which are deemed more effective take over and begin to dominate the search and computational time of SIM.
- Select Meme Frequency Analysis (Heat Map) tab to analyze search intensity of the dominating memes in SIM in the heat map as shown in Figure.
- Repeat step 1 to 7 to perform algorithm analysis of SAM scheduler on A-n69-k9 problem instance. Figures show the results of meme frequency analysis in stacked chart and heat map.
It can be seen how differently SAM scheduler behaves on the same problem instance. From algorithm analysis, meme selection adaptive MA such as SIM behaves quite differently from memeplex-based adaptive MA such as SAM in terms of meme deployment.
- Repeat step 1 to 7 to perform algorithm analysis of SIM scheduler on E-n101-k8 problem instance. Figures show the results of meme frequency analysis in stacked chart and heat map.
As it can be seen, SIM converge to some meme it deems more effective, but it varies from the case of A-n69-k9 problem instance.