Distance Evaluated Simulated Kalman Filter with State Encoding for Combinatorial Optimization Problems

  • Authors

    • Zulkifli Md Yusof
    • Zuwairie Ibrahim
    • Asrul Adam
    • Kamil Zakwan Mohd Azmi
    • Tasiransurini Ab Rahman
    • Badaruddin Muhammad
    • Nor Azlina Ab Aziz
    • Nor Hidayati Abd Aziz
    • Norrima Mokhtar
    • Mohd Ibrahim Shapiai
    • Mohd Saberi Muhammad
    2018-11-30
    https://doi.org/10.14419/ijet.v7i4.27.22431
  • combinatorial optimization, distance evaluated, simulated Kalman filter, state encoding, travelling salesman problem

  • Abstract

    Simulated Kalman Filter (SKF) is a population-based optimization algorithm which exploits the estimation capability of Kalman filter to search for a solution in a continuous search space. The SKF algorithm only capable to solve numerical optimization problems which involve continuous search space. Some problems, such as routing and scheduling, involve binary or discrete search space. At present, there are three modifications to the original SKF algorithm in solving combinatorial optimization problems. Those modified algorithms are binary SKF (BSKF), angle modulated SKF (AMSKF), and distance evaluated SKF (DESKF). These three combinatorial SKF algorithms use binary encoding to represent the solution to a combinatorial optimization problem. This paper introduces the latest version of distance evaluated SKF which uses state encoding, instead of binary encoding, to represent the solution to a combinatorial problem. The algorithm proposed in this paper is called state-encoded distance evaluated SKF (SEDESKF) algorithm. Since the original SKF algorithm tends to converge prematurely, the distance is handled differently in this study. To control and exploration and exploitation of the SEDESKF algorithm, the distance is normalized. The performance of the SEDESKF algorithm is compared against the existing combinatorial SKF algorithm based on a set of Traveling Salesman Problem (TSP).   

     

     

     

  • References

    1. [1] Rani MR, Selamat H, Zamzuri H & Ibrahim Z (2012), Multi-objective Optimization for PID Controller Tuning using the Global Ranking Genetic Algorithm, International Journal of Innovative Computing, Information and Control, Vol. 8, Issue 1, pp. 269-284.

      [2] Leung FHF, Lam HK, Ling SH & Tam PKS (2003), Tuning of the Structure and Parameters of a Neural Network using an Improved Genetic Algorithm, IEEE Transaction on Neural Networks, Vol. 14, Issue 1, pp. 79-88.

      [3] Roshanaei M, Lucas C & Mehrabian AR (2009), Adaptive Beamforming using a Novel Numerical Optimisation Algorithm, IET Microwaves, Antennas & Propagation, Vol. 3, Issue 5, pp. 765-773.

      [4] Li YL, Shao W, You L & Wang BZ (2013), An Improved PSO Algorithm and Its Application to UWB Antenna Design, IEEE Antennas and Wireless Propagation Letters, Vol. 12, pp. 1236-1239.

      [5] Valenzuela CL & Jones AJ (1993), Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSP, Evolutionary Computation, Vol. 1, Issue 4, pp. 313-333.

      [6] Pedraza G, Diaz M & Lombera H (2016), An Approach for Assembly Sequence Planning by Genetic Algorithms, IEEE Latin America Transactions, Vol. 14, Issue 5, pp. 2066-2071.

      [7] Montoya, J, Rathinam S & Wood Z (2014), Multiobjective Departure Runway Scheduling using Dynamic Programming, IEEE Transactions on Intelligent Transportation Systems, Vol. 15, Issue 1, pp. 399-413.

      [8] Mooney E & Dargen R (1996), Large-scale classroom scheduling, IIE Transactions, Vol. 28, No. 5, pp. 369-378.

      [9] Uttraphan C, Shaikh-Husin N & Khalil Hani M, An Optimization Algorithm for Simultaneous Routing and Buffer Insertion with Delay-power Constraints in VLSI Layout Design, Fifteenth International Symposium on Quality Electronics Design, (2014), pp. 357-364.

      [10] Jaffel Z & Farah M, A Symbiotic Organisms Search Algorithm for Feature Selection in Satellite Image Classification, 2018 4th International Conference on Advanced Technologies for Signal and Image Processing, (2018), pp. 1-5.

      [11] Goldberg DE & Holland JH (1988), Genetic Algorithms and Machine Learning, Machine Learning, Vol. 3, Issue 2-3, pp. 95-99.

      [12] Dorigo M, Maniezzo V & Colorni A (1996), Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 26, Issue 1, pp. 29-41.

      [13] Ibrahim Z, Abdul Aziz NH, Ab. Aziz NA, Razali S, Shapiai MI, Nawawi SW & Mohamad MS (2015), A Kalman Filter Approach for Solving Unimodal Optimization Problems, ICIC Express Letters, Vol. 9, Issue 12, pp. 3415-3422.

      [14] Ibrahim Z, Abdul Aziz NH, Ab. Aziz NA, Razali R, Mohamad MS (2016), Simulated Kalman Filter: A Novel Estimation-Based Metaheuristic Optimization Algorithm, Advance Science Letters, Vol. 22, pp. 2941-2946.

      [15] Kalman RE (2011), A New Approach to Linear Filtering and Prediction Problems, ASME Journal of Basic Engineering, Vol. 82, No. 1, pp. 35-45.

      [16] Muhammad B, Mat Jusof MF, Shapiai MI, Adam A, Md Yusof Z, Mohd Azmi KZ, Abdul Aziz NH, Ibrahim Z & Mokhtar N, Feature Selection using Binary Simulated Kalman Filter for Peak Classification of EEG Signals, 2018 8th International Conference on Intelligent Systems, Modelling and Simulation, (2018), pp. 1-6.

      [17] Adam A, Ibrahim Z, Mokhtar N, Shapiai MI, Mubin M & Saad I (2016), Feature Selection using Angle Modulated Simulated Kalman Filter for Peak Classification of EEG Signals, SpringerPlus, Vol. 5, No. 1580.

      [18] Lazarus K, Noordin NH, Mat Jusof MF, Ibrahim Z, & Abas KH (2017), Adaptive Beamforming Algorithm Based on a Simulated Kalman Filter, International Journal of Simulation: Systems, Science and Technology, Vol. 18, No. 4, pp. 10.1-10.5.

      [19] Lazarus K, Noordin NH, Mohd Azmi KZ, Abd Aziz NH & Ibrahim Z, Adaptive Beamforming Algorithm based on Generalized Opposition-based Simulated Kalman Filter, The National Conference for Postgraduate Research, Pekan, Pahang, (2016), pp. 1-9.

      [20] Lazarus K, Noordin NH, Ibrahim Z, Mat Jusof MF, Mohd Faudzi MA, Subari N, and Mohd Azmi KZ, An Opposition-Based Simulated Kalman Filter Algorithm for Adaptive Beamforming, IEEE International Conference on Applied System Innovation, (2017), pp. 91-94.

      [21] Lazarus K, Noordin NH, Ibrahim Z & Abas KH, Adaptive Beamforming Algorithm based on Simulated Kalman Filter, Asia Multi Conference on Modelling and Simulation, (2016), pp. 19-23.

      [22] Abd Aziz NH, Ab. Aziz NA, Ibrahim Z, Razali S, Abas KH, Mohamad MS, A Kalman Filter Approach to PCB Drill Path Optimization Problem, IEEE Conference on Systems, Process and Control, (2016), pp. 33-36.

      [23] Abdul Aziz NH, Ibrahim Z, Ab. Aziz NA, Md Yusof Z & Mohamad MS (2018), Single-Solution Simulated Kalman Filter Algorithm for Routing in Printed Circuit Board Drilling Process, Intelligent Manufacturing and Mechatronics, pp. 649-655.

      [24] Mustapa A, Md Yusof Z, Adam A, Muhammad B & Ibrahim Z (2018), Solving Assembly Sequence Planning using Angle Modulated Simulated Kalman Filter, IOP Conference Series: Materials, Science, and Engineering, Vol. 319, No. 012044.

      [25] Md Yusof Z, Satiman SN, Mohd Azmi KZ Badaruddin Muhammad, Saifudin Razali, Zuwairie Ibrahim, Zulfakar Aspar, and Suraya Ismail, Solving Airport Gate Allocation Problem using Simulated Kalman Filter, International Conference on Knowledge Transfer, (2015), pp. 121-127.

      [26] Mohd Azmi KZ, Md Yusof Z, Satiman SN, Muhammad B, Razali S, Ibrahim Z, Ab. Aziz NA & Abd Aziz NH, Solving Airport Gate Allocation Problem Using Angle Modulated Simulated Kalman Filter, The National Conference for Postgraduate Research, Pekan, Pahang, Malaysia, (2016), pp. 875-885.

      [27] Ann NQ, Pebrianti D, Bayuaji L, Daud MR, Samad R, Ibrahim Z, Hamid R & Syafrullah M (2018), SKF-Based Image Template Matching for Distance Measurement by using Stereo Vision, Intelligent Manufacturing and Mechatronics, pp. 439-447.

      [28] Ann NQ, Pebrianti D, Ibrahim Z, Mat Jusof MF, Bayuaji L, and Abdullah NRH (2018), Illumination-Invariant Image Matching Based on Simulated Kalman Filter (SKF), Journal of Telecommunication, Electronics and Computer Engineering, Vol. 10, No. 1-3, pp. 31-36.

      [29] Muhammad B, Mohd Azmi KZ, Ibrahim Z, Mohd Faudzi AA & Pebrianti D, Simultaneous Computation of Model Order and Parameter Estimation for System Identification Based on Opposition-Based Simulated Kalman Filter, SICE International Symposium on Control Systems 2018, March 9-11, Tokyo, Japan, (2018), pp. 105-112.

      [30] Mohd Azmi KZ, Ibrahim Z, Pebrianti D & Mohamad MS (2017), Simultaneous Computation of Model Order and Parameter Estimation for ARX Model Based on Single and Multi Swarm Simulated Kalman Filter, Journal of Telecommunication, Electronic, and Computer Engineering, Vol. 9, No. 1-3, pp. 151-155.

      [31] Muhammad B, Pebrianti D, Abdul Ghani N, Abdul Aziz NH, Ab. Aziz NA, Mohamad MS, Shapiai MI & Ibrahim Z, An Application of Simulated Kalman Filter Optimization Algorithm for Parameter Tuning in Proportional-Integral-Derivative Controllers for Automatic Voltage Regulator System, SICE International Symposium on Control Systems 2018, March 9-11, Tokyo, Japan, (2018), pp. 113-120.

      [32] Abd Aziz NH, Ibrahim Z, Razali S, Bakare TA & Ab. Aziz NA, How Important the Error Covariance in Simulated Kalman Filter?, The National Conference for Postgraduate Research, Pekan, Pahang, (2016), pp. 315-320.

      [33] Abdul Aziz NH, Ab. Aziz NA, Mat Jusof MF, Razali S, Ibrahim Z, Adam A & Shapiai MI, An analysis on the Number of Agents Towards the Performance of the Simulated Kalman Filter Optimizer, 2018 8th International Conference on Intelligent Systems, Modelling and Simulation, (2018), pp. 16-21.

      [34] Abdul Aziz NH, Ibrahim Z, Ab. Aziz NA & Razali S (2017), Parameter-less Simulated Kalman Filter, International Journal of Software Engineering and Computer Systems, Vol. 3, pp. 129-137.

      [35] Abd Aziz NH, Ab. Aziz NA, Ibrahim Z, Razali S, Mat Jusof MF, Abas KH, Mohamad MS & Mokhtar N, Simulated Kalman Filter with Randomized Q and R Parameters, International Conference on Artificial Life and Robotics, (2017) pp. 711-714.

      [36] Badaruddin Muhammad, Zuwairie Ibrahim, Mohd Falfazli Mat Jusof, Nor Azlina Ab Aziz, Nor Hidayati Abd Aziz, and Norrima Mokhtar, A Hybrid Simulated Kalman Filter - Gravitational Search Algorithm (SKF-GSA), International Conference on Artificial Life and Robotics, (2017), pp. 707-710.

      [37] Muhammad B, Ibrahim I, Mohd Azmi KZ, Abas KH, Ab. Aziz NA, Abd Aziz NH & Mohamad MS, Performance Evaluation of Hybrid SKF Algorithms: Hybrid SKF-PSO and Hybrid SKF-GSA, The National Conference for Postgraduate Research, Pekan, Pahang, Malaysia, (2016), pp. 865-874.

      [38] Muhammad B, Ibrahim Z, Mohd Azmi KZ, Abas KH, Ab. Aziz NA, Abd Aziz NH & Mohamad MS, Four Different Methods to Hybrid Simulated Kalman Filter (SKF) with Particle Swarm Optimization (PSO), The National Conference for Postgraduate Research, Pekan, Pahang, Malaysia, (2016), pp. 843-853.

      [39] Muhammad B, Ibrahim Z, Mohd Azmi KZ, Abas KH, Ab Aziz NA, Abd Aziz NH & Mohamad MS, Four Different Methods to Hybrid Simulated Kalman Filter (SKF) with Gravitational Search Algorithm (GSA), The National Conference for Postgraduate Research, Pekan, Pahang, Malaysia, (2016), pp. 854-864.

      [40] Muhammad B, Ibrahim Z, Ghazali KH, Mohd Azmi KZ, Ab. Aziz NA, Abd Aziz NH & Mohamad MS (2015), A New Hybrid Simulated Kalman Filter and Particle Swarm Optimization for Continuous Numerical Optimization Problems, ARPN Journal of Engineering and Applied Sciences, Vol. 10, No. 22, pp. 17171-17176.

      [41] Md Yusof Z, Ibrahim I, Satiman SN, Ibrahim Z, Abd Aziz NH, & Ab Aziz NA, BSKF: Binary Simulated Kalman Filter, Third International Conference on Artificial Intelligence, Modelling and Simulation, (2015), pp. 77-81.

      [42] Md Yusof Z, Ibrahim I, Ibrahim Z, Abas KH, Ab Aziz NA, Abd Aziz NH & Mohamad MS, Local Optimum Distance Evaluated Simulated Kalman Filter for Combinatorial Optimization Problems, The National Conference for Postgraduate Research, Pekan, Pahang, Malaysia, (2016), pp. 892-901.

      [43] Md Yusof Z, Ibrahim Z, Ibrahim I, Mohd Azmi KZ, Ab. Aziz NA, Abd Aziz NH & Mohamad MS (2016), Distance Evaluated Simulated Kalman Filter for Combinatorial Optimization Problems, ARPN Journal of Engineering and Applied Sciences, Vol. 11, No. 7, pp. 4904-4910.

      [44] Md Yusof Z, Ibrahim Z, Ibrahim I, Mohd Azmi KZ, Ab. Aziz NA, Abd Aziz NH & Mohamad MS (2016), Angle Modulated Simulated Kalman Filter Algorithm for Combinatorial Optimization Problems, ARPN Journal of Engineering and Applied Sciences, Vol. 11, No. 7, pp. 4854-4859.

      [45] Ibrahim I, Md Yusof Z, Nawawi SW, Rahim, MAA, Khalil K, Ahmad H & Ibrahim Z, A Novel Multi-state Particle Swarm Optimization for Discrete Combinatorial Optimization Problems, Fourth International Conference on Computational Intelligence, Modelling and Simulation, (2012), pp. 18-23.

      [46] Ibrahim I, Ahmad H, Ibrahim Z, & Md Yusof Z (2015), An Improved Multi-State Particle Swarm Optimization for Discrete Combinatorial Optimization Problems, International Journal of Simulation - Systems, Science and Technology, Vol. 16, No. 6, pp. 14.1-14.8.

      [47] Ibrahim I, Ahmad H, Ibrahim Z, Mat Jusoh MF, Zulkifli Md. Yusof, Nawawi SW, Khalil K & Abdul Rahim MA (2014), Multi-State Particle Swarm Optimization for Discrete Combinatorial Optimization Problem, International Journal of Simulation - Systems, Science and Technology, Vol. 15, No. 1, pp. 15-25.

      [48] Ibrahim I, Ibrahim Z, Ahmad H & Md Yusof Z, An Improved Multi-State Particle Swarm Optimization for Discrete Optimization Problems, The 7th International Conference on Computational Intelligence, Communication Systems, and Networks, (2015), pp. 3-8.

      [49] Ibrahim I, Ibrahim Z, Ahmad H & Md. Yusof Z, A Multi-State Gravitational Search Algorithm for Combinatorial Optimization Problems, The 7th International Conference on Computational Intelligence, Communication Systems, and Networks, (2015), pp. 9-14.

      [50] Ibrahim I, Ahmad H, Ibrahim Z & Md Yusof Z (2015), A Novel Multi-State Gravitational Search Algorithm for Discrete Optimization Problems, International Journal of Simulation - Systems, Science and Technology, Vol. 16, No. 6, pp. 15.1-15.8.

      [51] Ismail Ibrahim, Zuwairie Ibrahim, Hamzah Ahmad, and Zulkifli Md Yusof (2015), An Assembly Sequence Planning Approach with a Multi-State Gravitational Search Algorithm, ARPN Journal of Engineering and Applied Sciences, Vol. 10, No. 22, pp. 10709-10715.

      [52] Ibrahim I, Ibrahim Z, Ahmad H, Mat Jusof MF, Md. Yusof Z, Nawawi SW & Marizan Mubin M (2015), An Assembly Sequence Planning Approach with a Rule-based Multi-State Gravitational Search Algorithm, The International Journal of Advanced Manufacturing Technology, Vol. 79, Issue 5, pp. 1363-1376.

      [53] Ibrahim I, Ibrahim Z, Ahmad H & Md Yusof Z, Rule-Based Multi-State Gravitational Search Algorithm for Discrete Optimization Problem, The 4th International Conference on Software Engineering and Computer Systems (ICSECS2015), Kuantan, Pahang, (2015).

      [54] Leonard BJ & Engelbrecht AP (2014), Angle Modulated Particle Variants, Lecture Notes on Computer Science, Vol. 8667, pp. 38-49.

      [55] http://www.iwr.uni-heidelberg.de/groups/comopt/software

  • Downloads

  • How to Cite

    Md Yusof, Z., Ibrahim, Z., Adam, A., Zakwan Mohd Azmi, K., Ab Rahman, T., Muhammad, B., Azlina Ab Aziz, N., Hidayati Abd Aziz, N., Mokhtar, N., Ibrahim Shapiai, M., & Saberi Muhammad, M. (2018). Distance Evaluated Simulated Kalman Filter with State Encoding for Combinatorial Optimization Problems. International Journal of Engineering & Technology, 7(4.27), 22-29. https://doi.org/10.14419/ijet.v7i4.27.22431

    Received date: 2018-11-30

    Accepted date: 2018-11-30

    Published date: 2018-11-30