Staff View: A discrete simulated kalman filter optimizer for combinatorial optimization problems

A discrete simulated kalman filter optimizer for combinatorial optimization problems

Combinatorial optimization problems are ubiquitous in many fields, including healthcare, economics, engineering, manufacturing, and others. A solution to a combinatorial optimization problem is frequently expressed in terms of a permutation, arrangement, or combination of elements. Due to the practi...

Full description

Saved in:

Bibliographic Details
Main Author:	Suhazri Amrin, Rahmad
Format:	Thesis
Language:	English
Published:	2022
Subjects:	T Technology (General) TA Engineering (General). Civil engineering (General)
Online Access:	http://umpir.ump.edu.my/id/eprint/38450/1/A%20discrete%20simulated%20kalman%20filter%20optimizer%20for%20combinatorial%20optimization%20problems.ir.pdf http://umpir.ump.edu.my/id/eprint/38450/
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my.ump.umpir.38450
record_format	eprints
spelling	my.ump.umpir.384502023-08-25T02:13:14Z http://umpir.ump.edu.my/id/eprint/38450/ A discrete simulated kalman filter optimizer for combinatorial optimization problems Suhazri Amrin, Rahmad T Technology (General) TA Engineering (General). Civil engineering (General) Combinatorial optimization problems are ubiquitous in many fields, including healthcare, economics, engineering, manufacturing, and others. A solution to a combinatorial optimization problem is frequently expressed in terms of a permutation, arrangement, or combination of elements. Due to the practical significance of this problem in real-world issues, numerous algorithms have been proposed to solve it. These algorithms specifically refer to those that operate in discrete search space, often known as combinatorial algorithms. Another type of algorithm is called numerical algorithms. These algorithms were built specifically to address numerical optimization problems. In the last few decades, significant research effort has been spent on the development of numerical algorithms, particularly for solving combinatorial problems. An example of a numerical algorithm is the simulated Kalman filter (SKF). Various method has been introduced as an extension of a numerical algorithm to adapt it to a discrete search space. There are currently three extensions to the SKF, resulting in three combinatorial algorithms: the binary SKF (BSKF), the distance evaluated SKF (DESKF), and the angle modulated SKF (AMSKF). However, these extensions may result in increased execution times for the algorithm. In this research, a new combinatorial algorithm named discrete simulated Kalman filter optimizer (DSKFO) is proposed to solve combinatorial optimization problem. This new algorithm is originated by the concept of the simulated Kalman filter (SKF). Due to the limitation of the SKF algorithm which only able to operate in continuous search space, the proposed algorithm makes use of a new interpretation that incorporates mutation and Hamming distance, allowing the proposed algorithm to function in discrete search space. In this research, three combinatorial problems namely the travelling salesman problem (TSP), assembly sequence planning (ASP), and the hole drilling proble are used to evaluate the proposed algorithm. Two types of analysis are used to evaluate the proposed algorithm. First, the DSKFO algorithm is used to solve the travelling salesman problem (TSP), and then the algorithm's execution time is measured. Existing SKF methods are then compared to the findings of the DSKFO algorithm. DSKFO performs the fastest, requiring just 13 seconds to solve a small TSP instance such as eil51, whereas DESKF, AMSKF, BSKF, and SEDESKF require around 36, 42, 34, and 14 seconds, respectively. To solve larger TSP instance such as rl1889, DSKFO requires 139 seconds to execute a single run, whereas DESKF, AMSKF, BSKF, and SEDESKF require around 1587, 1590, 2418, and 208 seconds, respectively. For the second analysis, the performance of the proposed method is evaluated using three combinatorial problems: the travelling salesman problem (TSP), the assembly sequence planning (ASP), and the hole drilling problem. The results are compared to four previously published combinatorial SKFs: the BSKF, the AMSKF, the DESKF, and the SEDESKF. The DSKFO may be considered the best algorithm for solving the TSP and hole drilling problem, as it has the highest number of best performances. For solving the ASP, the DSKFO ranked third, while the AMSKF came in first, followed by the DESKF in second. 2022-08 Thesis NonPeerReviewed pdf en http://umpir.ump.edu.my/id/eprint/38450/1/A%20discrete%20simulated%20kalman%20filter%20optimizer%20for%20combinatorial%20optimization%20problems.ir.pdf Suhazri Amrin, Rahmad (2022) A discrete simulated kalman filter optimizer for combinatorial optimization problems. Masters thesis, Universiti Malaysia Pahang (Contributors, Thesis advisor: Zuwairie, Ibrahim).
institution	Universiti Malaysia Pahang
building	UMP Library
collection	Institutional Repository
continent	Asia
country	Malaysia
content_provider	Universiti Malaysia Pahang
content_source	UMP Institutional Repository
url_provider	http://umpir.ump.edu.my/
language	English
topic	T Technology (General) TA Engineering (General). Civil engineering (General)
spellingShingle	T Technology (General) TA Engineering (General). Civil engineering (General) Suhazri Amrin, Rahmad A discrete simulated kalman filter optimizer for combinatorial optimization problems
description	Combinatorial optimization problems are ubiquitous in many fields, including healthcare, economics, engineering, manufacturing, and others. A solution to a combinatorial optimization problem is frequently expressed in terms of a permutation, arrangement, or combination of elements. Due to the practical significance of this problem in real-world issues, numerous algorithms have been proposed to solve it. These algorithms specifically refer to those that operate in discrete search space, often known as combinatorial algorithms. Another type of algorithm is called numerical algorithms. These algorithms were built specifically to address numerical optimization problems. In the last few decades, significant research effort has been spent on the development of numerical algorithms, particularly for solving combinatorial problems. An example of a numerical algorithm is the simulated Kalman filter (SKF). Various method has been introduced as an extension of a numerical algorithm to adapt it to a discrete search space. There are currently three extensions to the SKF, resulting in three combinatorial algorithms: the binary SKF (BSKF), the distance evaluated SKF (DESKF), and the angle modulated SKF (AMSKF). However, these extensions may result in increased execution times for the algorithm. In this research, a new combinatorial algorithm named discrete simulated Kalman filter optimizer (DSKFO) is proposed to solve combinatorial optimization problem. This new algorithm is originated by the concept of the simulated Kalman filter (SKF). Due to the limitation of the SKF algorithm which only able to operate in continuous search space, the proposed algorithm makes use of a new interpretation that incorporates mutation and Hamming distance, allowing the proposed algorithm to function in discrete search space. In this research, three combinatorial problems namely the travelling salesman problem (TSP), assembly sequence planning (ASP), and the hole drilling proble are used to evaluate the proposed algorithm. Two types of analysis are used to evaluate the proposed algorithm. First, the DSKFO algorithm is used to solve the travelling salesman problem (TSP), and then the algorithm's execution time is measured. Existing SKF methods are then compared to the findings of the DSKFO algorithm. DSKFO performs the fastest, requiring just 13 seconds to solve a small TSP instance such as eil51, whereas DESKF, AMSKF, BSKF, and SEDESKF require around 36, 42, 34, and 14 seconds, respectively. To solve larger TSP instance such as rl1889, DSKFO requires 139 seconds to execute a single run, whereas DESKF, AMSKF, BSKF, and SEDESKF require around 1587, 1590, 2418, and 208 seconds, respectively. For the second analysis, the performance of the proposed method is evaluated using three combinatorial problems: the travelling salesman problem (TSP), the assembly sequence planning (ASP), and the hole drilling problem. The results are compared to four previously published combinatorial SKFs: the BSKF, the AMSKF, the DESKF, and the SEDESKF. The DSKFO may be considered the best algorithm for solving the TSP and hole drilling problem, as it has the highest number of best performances. For solving the ASP, the DSKFO ranked third, while the AMSKF came in first, followed by the DESKF in second.
format	Thesis
author	Suhazri Amrin, Rahmad
author_facet	Suhazri Amrin, Rahmad
author_sort	Suhazri Amrin, Rahmad
title	A discrete simulated kalman filter optimizer for combinatorial optimization problems
title_short	A discrete simulated kalman filter optimizer for combinatorial optimization problems
title_full	A discrete simulated kalman filter optimizer for combinatorial optimization problems
title_fullStr	A discrete simulated kalman filter optimizer for combinatorial optimization problems
title_full_unstemmed	A discrete simulated kalman filter optimizer for combinatorial optimization problems
title_sort	discrete simulated kalman filter optimizer for combinatorial optimization problems
publishDate	2022
url	http://umpir.ump.edu.my/id/eprint/38450/1/A%20discrete%20simulated%20kalman%20filter%20optimizer%20for%20combinatorial%20optimization%20problems.ir.pdf http://umpir.ump.edu.my/id/eprint/38450/
_version_	1775622267556855808
score	13.211869

A discrete simulated kalman filter optimizer for combinatorial optimization problems

Similar Items