Multi-state PSO GSA for solving discrete combinatorial optimization problems

There are various meta-heuristics exist in literature nowadays. However, not all metaheuristics were originally d~veloped to operate in discrete search space. Two examples of meta-heuristics are Particle swarm optimization (PSO) and gravitational search algorithm (GSA), which are based on the social...

Full description

Saved in:

Bibliographic Details
Main Author:	Ismail, Ibrahim
Format:	Thesis
Language:	English
Published:	2016
Subjects:	TK Electrical engineering Electronics Nuclear engineering
Online Access:	http://umpir.ump.edu.my/id/eprint/17603/1/Multi-state%20PSO%20GSA%20for%20solving%20discrete%20combinatorial%20optimization%20problems.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-ump-ir.17603
record_format	uketd_dc
spelling	my-ump-ir.176032023-05-24T03:13:05Z Multi-state PSO GSA for solving discrete combinatorial optimization problems 2016-08 Ismail, Ibrahim TK Electrical engineering. Electronics Nuclear engineering There are various meta-heuristics exist in literature nowadays. However, not all metaheuristics were originally d~veloped to operate in discrete search space. Two examples of meta-heuristics are Particle swarm optimization (PSO) and gravitational search algorithm (GSA), which are based on the social behavior of bird flocks and the Newton's law of gravity and the law of motion, respectively. In order to solve discrete combinatorial optimization problems (COPs) using meta-heuristics, modification or enhancement is needed. In the context of the modification, a variety of discretization approaches have been proposed. Inspired by the design of a sequential circuit of digital system, a new discretization approach that leads to the establishment of a complete model of multi-state has been proposed. Based on the multi-state model, a multi-state search space is successfully built using the following two features; a current state and a radius. The multistate model is then implemented in PSO and GSA. As a consequence, multi-state particle swarm optimization (MSPSO) and multi-state gravitational search algorithm (MSGSA) are developed. In the MSPSO and the MSGSA, the radius is represented by new velocity value. The extended version of the multi-state model is then formulated by introducing an embedded rule that ensures the updated solutions to be formed by unrepeated states. As a consequence, multi-state particle swarm optimization with an embedded rule (MSPSOER) and multi-state gravitational search algorithm with an embedded rule (MSGSAER) are developed. These four algorithms can be used to solve discrete combinatorial optimization problems (COPs). To evaluate the performances of the proposed algorithms, several experiments using eighteen sets of selected benchmarks instances of Travelling salesman problem (TSP) and a case study of assembly sequence planning (ASP) problem are conducted. The experimental results showed the newly introduced multi-state PSO GSA are promising compared to binary particle swarm optimization (BPSO) and binary gravitational search algorithm (BGSA) for the TSP and consistently outperformed simulated annealing (SA), genetic algorithm (GA), and BPSO for the ASP in finding optimal solutions. 2016-08 Thesis http://umpir.ump.edu.my/id/eprint/17603/ http://umpir.ump.edu.my/id/eprint/17603/1/Multi-state%20PSO%20GSA%20for%20solving%20discrete%20combinatorial%20optimization%20problems.pdf pdf en public phd doctoral Universiti Malaysia Pahang Faculty of Electrical and Electronics Engineering
institution	Universiti Malaysia Pahang Al-Sultan Abdullah
collection	UMPSA Institutional Repository
language	English
topic	TK Electrical engineering Electronics Nuclear engineering
spellingShingle	TK Electrical engineering Electronics Nuclear engineering Ismail, Ibrahim Multi-state PSO GSA for solving discrete combinatorial optimization problems
description	There are various meta-heuristics exist in literature nowadays. However, not all metaheuristics were originally d~veloped to operate in discrete search space. Two examples of meta-heuristics are Particle swarm optimization (PSO) and gravitational search algorithm (GSA), which are based on the social behavior of bird flocks and the Newton's law of gravity and the law of motion, respectively. In order to solve discrete combinatorial optimization problems (COPs) using meta-heuristics, modification or enhancement is needed. In the context of the modification, a variety of discretization approaches have been proposed. Inspired by the design of a sequential circuit of digital system, a new discretization approach that leads to the establishment of a complete model of multi-state has been proposed. Based on the multi-state model, a multi-state search space is successfully built using the following two features; a current state and a radius. The multistate model is then implemented in PSO and GSA. As a consequence, multi-state particle swarm optimization (MSPSO) and multi-state gravitational search algorithm (MSGSA) are developed. In the MSPSO and the MSGSA, the radius is represented by new velocity value. The extended version of the multi-state model is then formulated by introducing an embedded rule that ensures the updated solutions to be formed by unrepeated states. As a consequence, multi-state particle swarm optimization with an embedded rule (MSPSOER) and multi-state gravitational search algorithm with an embedded rule (MSGSAER) are developed. These four algorithms can be used to solve discrete combinatorial optimization problems (COPs). To evaluate the performances of the proposed algorithms, several experiments using eighteen sets of selected benchmarks instances of Travelling salesman problem (TSP) and a case study of assembly sequence planning (ASP) problem are conducted. The experimental results showed the newly introduced multi-state PSO GSA are promising compared to binary particle swarm optimization (BPSO) and binary gravitational search algorithm (BGSA) for the TSP and consistently outperformed simulated annealing (SA), genetic algorithm (GA), and BPSO for the ASP in finding optimal solutions.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Ismail, Ibrahim
author_facet	Ismail, Ibrahim
author_sort	Ismail, Ibrahim
title	Multi-state PSO GSA for solving discrete combinatorial optimization problems
title_short	Multi-state PSO GSA for solving discrete combinatorial optimization problems
title_full	Multi-state PSO GSA for solving discrete combinatorial optimization problems
title_fullStr	Multi-state PSO GSA for solving discrete combinatorial optimization problems
title_full_unstemmed	Multi-state PSO GSA for solving discrete combinatorial optimization problems
title_sort	multi-state pso gsa for solving discrete combinatorial optimization problems
granting_institution	Universiti Malaysia Pahang
granting_department	Faculty of Electrical and Electronics Engineering
publishDate	2016
url	http://umpir.ump.edu.my/id/eprint/17603/1/Multi-state%20PSO%20GSA%20for%20solving%20discrete%20combinatorial%20optimization%20problems.pdf
_version_	1783732020086571008

Multi-state PSO GSA for solving discrete combinatorial optimization problems

Similar Items