تحسين خوارزميات الحل التام والبحث المحلي لحل بعض مسائل الامثلية التوافقية == Improving Exact and Local Search Algorithms for Solving Some Combinatorial Optimization Problems
Author name:
فائز حسن علي
Supervisor name:
طارق صالح عبد الرزاق
General topic:
Mathematics
Specific topic:
Numerical Optimization
Degree:
Doctorate
University:
Mustansiriyah University - College Of Education For Pure Sciences - Department Of Mathematics
Language:
English
University location:
Baghdad
First pages:
27T1174 - p.pdf
Abstract:
In mathematics and computer science, an optimization problem (OP) is the problem of finding the best solution from all feasible solutions. OPs can be divided into two categories depending on whether the variables are continuous or discrete. An OP with discrete variables is known as a combinatorial optimization problem (COP). In a COP, we are looking for an object such as an integer, permutation or graph from a finite set.The aim of the research presented in this thesis is to investigate the use of various optimization exacts and heuristics to solve the COP's. This thesis presented in six chapters.In this thesis we interest in discussing three samples of COP; machine scheduling problem (MSP), transposition cipher problem (TCP) and aircraft landing problem (ALP).In the first two chapters, we discuss the main concepts of the COP, the three study cases, the basic techniques and methods for solving the COP respectively.In chapter three, we interesting in MSP, with multiple objective for the 1//(Ci,Ti) problem (P1) and 1//Ci+Ti problem (P3). We investigate the usefulness of precedence rules in solving (P1) and (P3). We found that the complete enumeration method (CEM) gives efficient (and optimal) solutions for (P1) (and (P3)) with number of jobs (n)10, and branch and bound (BAB) gives efficient solutions for (P1) with n15 and optimal solution for (P3) with n80. In addition, we use the local search methods (LSM), to solve the two problems, represented by genetic algorithm (GA) and particle swarm optimization (PSO) with n2000. In general we conclude that PSO serves better than GA. Lastly, a neural network (NN) is constructed to solve problems (P1) and (P3). Two learning algorithms are used to learn the NN; pack propagation (PB) and PSO with and without depending on successive rules (SR). We see that PSO is better than BP in learning NN to obtaining good results.In chapter four, we suggest a new direction in cryptanalysis of TCP, we suggest using the techniques of COP to solve TCP in another word, the TCP treated as one of COP. First a new mathematical formulation for TCP is introduced and proposed some new tools of TCP cryptanalysis. The CEM and modified BAB are developed by using SR to obtain the multi digits CEM (MDCEM) and MDBAB which are helpful in decreasing the CPU time. Classical bees' algorithm (CBA) and shifted key BA (SKBA) are improving the cryptanalysis results. To increase the performance of the mentioned algorithms we construct cryptanalysis system for TCP to find exact solution (as possible) for n20 in reasonable time, which is called SR keys BA (SRKBA). The main result of this thesis is suggesting a general solving system for COP specially, when the problem submits to SR.Chapter five focused in one of the important problems of COP; ALP. A new improvement in a heuristic method, called parallel improving algorithm (PIA), is introduced, the new algorithm called modified PIA (MPIA) which is serves better than PIA. The CEM is used to solve ALP using two techniques; exhaustive search method (ESM) which gives optimal solution but in unreasonable time for n>9 while MPIA gives approximation solutions for n9 in 6 seconds. Lastly, hybridization is proposed between MPIA and CBA, which is called improvement CBA (ICBA). ICBA gives optimal solutions in solving ALP for n<50 and near optimal for n=50.In chapter six, some conclusions together with some suggestions for future researches have been given.The exact and heuristics methods all were tested by programming them using version 10.0 of Delphi Language and MATLAB, and running on Processor Intel(R) Core (TM) i3 CPU, 2.53 GHz, Core(s), with Ram 1.21 GB computer.
