Annals of Computer Science and Information Systems, Volume 18

DOI: http://dx.doi.org/10.15439/2019F191

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 47–56 (2019)

Full text

Abstract. In the recent years, it has been shown that real world-problems are often comprised of two, interdependent subproblems. Often, solving them independently does not lead to the solution to the entire problem. In this article, a Travelling Thief Problem is considered, which combines a Travelling Salesman Problem with a Knapsack Problem. A Non-Dominated Sorting Genetic Algorithm II (NSGA-II) is investigated, along with its recent modification - a Non-Dominated Tournament Genetic Algorithm (NTGA). Each method is investigated in two configurations. One, with generic representation, and genetic operators. The other, specialized to the given problem, to show how the specialization of genetic operators leads to better results. The impact of the modifications introduced by NTGA is verified. A set of Quality Measures is used to verify the convergence, and diversity of the resulting PF approximations, and efficiency of the method. A set of experiments is carried out. It is shown that both methods work almost the same when generic representation is used. However, NTGA outperforms classical NSGA-II in the specialized results.

References

1. Akbalik, Ayse, et al. "NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract." European Journal of Operational Research 257.2 (2017): 483-493.
2. Sanei, Masoud, et al. "Step fixed-charge solid transportation problem: a Lagrangian relaxation heuristic approach." Computational and Applied Mathematics 36.3 (2017): 1217-1237.
3. Mnich, Matthias, and Rene van Bevern. "Parameterized complexity of machine scheduling: 15 open problems." Computers & Operations Research (2018).
4. Blank, Julian, Kalyanmoy Deb, and Sanaz Mostaghim. "Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms." International Conference on Evolutionary Multi-Criterion Optimization. Springer, Cham, 2017.
5. Bonyadi, Mohammad Reza, Zbigniew Michalewicz, and Luigi Barone. "The travelling thief problem: The first step in the transition from theoretical problems to realistic problems." 2013 IEEE Congress on Evolutionary Computation. IEEE, 2013.
6. Bonyadi, Mohammad Reza, et al. "Evolutionary computation for multi-component problems: opportunities and future directions." Optimization in Industry. Springer, Cham, 2019. 13-30.
7. Martins, Marcella SR, et al. "HSEDA: a heuristic selection approach based on estimation of distribution algorithm for the travelling thief problem." Proceedings of the Genetic and Evolutionary Computation Conference. ACM, 2017.
8. Wagner, Markus. "Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem." International Conference on Swarm Intelligence. Springer, Cham, 2016.
9. Deb, Kalyanmoy, et al. "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE transactions on evolutionary computation 6.2 (2002): 182-197.
10. Laszczyk, Maciej, and Paweł B. Myszkowski. "Improved selection in evolutionary multi-objective optimization of Multi-Skill Resource-Constrained project scheduling problem." Information Sciences 481 (2019): 412-431.
11. Laszczyk, Maciej, and Paweł B. Myszkowski. "Survey of quality measures for multi-objective optimization. Construction of complementary set of multi-objective quality measures." Swarm and Evolutionary Computation (2019).
12. Polyakovskiy, Sergey, et al. "A comprehensive benchmark set and heuristics for the traveling thief problem." Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. ACM, 2014.
13. Wu, Junhua, et al. "Exact approaches for the travelling thief problem." Asia-Pacific Conference on Simulated Evolution and Learning. Springer, Cham, 2017.
14. Vieira, Daniel KS, et al. "A genetic algorithm for multi-component optimization problems: the case of the travelling thief problem." European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, Cham, 2017.
15. Wu, Junhua, et al. "Evolutionary computation plus dynamic programming for the bi-objective travelling thief problem." Proceedings of the Genetic and Evolutionary Computation Conference. ACM, 2018.
16. Whitley, L. Darrell, Timothy Starkweather, and D’Ann Fuquay. "Scheduling problems and traveling salesmen: The genetic edge recombination operator." ICGA. Vol. 89. 1989.
17. Marti, Luis, Eduardo Segredo, and Emma Hart. "Impact of selection methods on the diversity of many-objective Pareto set approximations." Procedia Computer Science 112 (2017): 844-853.
18. Yafrani, Mohamed, et al. "A hyperheuristic approach based on low-level heuristics for the travelling thief problem." Genetic Programming and Evolvable Machines 19.1-2 (2018): 121-150.
19. Cao, Yongtao, Byran J. Smucker, and Timothy J. Robinson. "On using the hypervolume indicator to compare Pareto fronts: Applications to multi-criteria optimal experimental design." J. of Stat. Planning and Inference 160 (2015): 60-74.
20. Durairaj, M., D. Sudharsun, and N. Swamynathan. "Analysis of process parameters in wire EDM with stainless steel using single objective Taguchi method and multi objective grey relational grade." Procedia Engineering 64 (2013): 868-877.
21. Lopez-Ibanez M., Paquete L., and Stutzle T. “Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization”, Experimental Methods for the Analysis of Optimization Algorithms (2010): 209-222.