Background Solving problems classified as either NP-complete or NP-hard has long been an active topic in the research community, and has brought about many new algorithms for approximating an optimal solution (basically the best possible solution). A fundamental aspect to consider when developing such an algorithm is how to represent the given solution. Finding the right encoding scheme is key for any algorithm to function as efficiently as possible. That being said, there appears to be a lack of research studies that offer a comprehensive comparison of these encoding schemes. Objectives This study sets out to provide an extensive comparative analysis of five already existing encoding schemes for a population-based meta-heuristic algorithm, with focus on two discrete combinatorial problems: the 1/0 knapsack problem and task scheduling problem. The most popular scheme of these will also be defined and determined by reviewing the literature. Methods The encoding schemes were implemented and incorporated into a recently proposed algorithm, known as the Coyote Optimization Algorithm. Their difference in performance were then compared through several experiments.On top of that, the popularity of said schemes were measured by their number of occurrences among a set of surveyed research studies (on the topic knapsack-problem). Conclusions When compared to the real-valued encoding scheme, we found that both qubits (smallest unit in quantum computing) and complex numbers were more efficient for solving the 1/0 knapsack problem, due to their broader search-space.Our chosen variant of the quantum-inspired encoding scheme contributed to a slightly better result than its complex-valued counterpart. The binary- and boolean encoding schemes worked great in conjunction with a repair function for the knapsack problem, to the extent that their produced solutions converged at a faster rate than the rest.Interestingly enough, the real-valued encoding scheme was by far the more popular choice of them all (as far as the knapsack problem is concerned), which we attribute to its generally simple and convenient implementation; and the fact that it has been around for longer. Finally, we saw that the matrix-based encoding scheme contributed to a faster convergence rate for approximate solutions to the task scheduling problem when the hardware for each resource differed greatly in computing capacity. On the other hand, the SPV (small position value) decoder for both the real-valued and complex-valued encoding schemes were more advantageous when the resources had near to identical computing power, as it is more suitable for distributing tasks equally.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:bth-18588 |
| Date | January 2019 |
| Creators | Pettersson, Richard |
| Publisher | Blekinge Tekniska Högskola, Institutionen för programvaruteknik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds