| Abstract [eng] |
Travelling salesman problem and graph coloring problem is widely known as the most applicable and used as a benchmark to measure the effectiveness of various heuristic algorithms. innovative idea to do away with a goal function (which originated in a whole widely different computer science field) was formed into a concrete implementation and applied to travelling salesman problem and graph coloring problem domain. In this thesis the search for anomalies in graph domain was extensively discussed as a valuable bridge to the idea of novelty search. The search for anomalies can help form new similarity functions, which are the main driving force behind novelty search. Moreover, it is the only loosely defined concept, which in turn results in its unpredictability. This is the point where creativity and science meet, which encourages even more experimentation with unusual similarity functions. Formalized novelty search is not effective in a general graph optimization case but is superior (compared with traditional heuristics) in specific case where graph is intentionally constructed to be hard to improve iteratively. In this thesis there was an experiment regarding the efficiency of traditional heuristic algorithms and the parameter influence of said algorithms. Furthermore, presented methodology of combining parameters was used to find a good enough combination of parameters which in turn lead to pretty fair comparison of the effectiveness of heuristic algorithms. Moreover, in this thesis there are several descriptions of similarity functions all of which are used during the novelty search experiment besides the similarity functions derived from various anomaly search algorithms. Also, a brand new archiving method is proposed in this thesis which simulates hierarchical fuzzy clustering by grouping similar solutions thus increasing the speed of the algorithm and providing a structure to the archive. Lastly, there are several modifications to the traditional heuristic algorithms proposed in this thesis. |
