Improving The Imperialist Competitive Algorithm To Find Nash Equilibrium Points In Crisis Management Problem

$42

Description

M.Sc. thesis

 In Information Technology Engineering

(Software Designing and Producing)

 

 

IMPROVING  THE IMPERIALIST COMPETITIVE ALGORITHM TO FIND NASH EQUILIBRIUM POINTS IN CRISIS MANAGEMENT PROBLEM

ABSTRACT

Problems that have several optimal points and all of that points help to solve it, is a multimodal optimization problem. In multimodal optimization, the user acquires more knowledge about different solutions for search space and it helps him to use another solution when this solution is not suitable for some reasons. The objective of the optimization techniques is maintaining diversity in the populations and between answer groups. also, the calculation of  Nash equilibrium points in non-cooperative multiplayer games is difficult. in games, when the number of players and their strategies and also game equilibrium points increases, mathematical algorithms are not able to identify all equilibrium points at a time because of difficulty in calculations. Evolutionary algorithms are a powerful search tool for solving these optimization problems.

The optimal allocation of resources to emergency locations in the event of multiple crises in an urban environment is an intricate problem, especially when the available resources are limited. In such a scenario, it is important to allocate emergency response units in a fair manner based on the criticality of the crisis events and their requests.

The Proposed algorithm, is improving the imperialist competitive algorithm to find Nash equilibrium points in crisis management problem. in this algorithm, optimums are searched in separate empires that are growing.to do this, we use an empire growth criterion for determining empire growth in development decades and then growing and unstable empires specifies, so the empires that evolved to a threshold  it means that it has an optimum so this optimum should save in the external storage, if an empire does not grow, that is unstable and it faces the revolution and will be demolished. after several algorithm iterations, saved answers in storage are all optimums of the problem.

In this thesis, The problem is formulated as a game-theoretic framework in which the crisis events are modeled as the players, the emergency response centers as the resource locations with emergency units to be Scheduled and the possible allocations as strategies.

In this problem we allocate some resources to each crisis , such that allocated resources to players (crisis) be the best possible combination and any other combination alter the situation to the worst status, these best combinations is not necessarily the same and they called Nash equilibrium points, we prove that the Lyapunov function return 0 for every such combination.

 References :

  • Gupta, , Ranganathan ,N.( 2007 ). “Multievent Crisis Management Using Noncooperative Multistep Games”, IEEE Press, VOL. 56, NO. 5
  • Das, S., Maity, S., Qu, B.Y., Suganthan, P.N. (2011). “Real-parameter evolutionary multimodal optimization — A survey of the state-of-the-art”, Swarm and Evolutionary Computation.
  • Fayek, M., M. Darwish, N., M. Ali, M.(2010). “Context-based clearing procedure: A niching method for genetic algorithms“, Journal of Advanced Research.
  • Ye, F., Qi, W., Xiao, J.(2011). ”Research of niching genetic algorithms for optimization in electromagnetics”, In: Science Direct, Procedia Engineering.
  • N.A. Pereira, C. , F. Sacco, W.(2008).”A parallel genetic algorithm with niching technique applied to a nuclear reactor core design optimization problem”, in: Science Direct, Progress in Nuclear Energy.
  • Yu ,E.L., Suganthan ,P.N.(2010). ”Ensemble of niching algorithms”, in: Information Sciences.
  • Jada, Ch., Yenala, H., Rachavarapu, K.K., Chittipolu, N. K.,Omkar ,S.N.(2012) “ Modified Roaming Optimization for Multi-modal Optima’’,in: Third International Conference on Emerging Applications of Information Technology,IEEE.
  • Das, S., Maity, S., Qu, B.Y. , Suganthan, P.N. (2011). “Real-parameter evolutionary multimodal optimization — A survey of the state-of-the-art”, Swarm and Evolutionary Computation.
  • Liu, Y. , Yan, Z., Li, W., Lv, M. , Yao, Y.(2010). “An Automatic Niching Particle Swarm for Multimodal Function Optimization”, In: Springer-Verlag Berlin Heidelberg.
  • Li, X.(2007).’’ A multimodal particle swarm optimizer based on fitness Euclidean-distance ratio’’,in: Proceedings of the 9th annual conference on Genetic and evolutionary computation,pp.78-85.
  • (2005).’’Dynamic multi-swarm particle swarm optimizer with local search’’, in: Evolutionary Computation,IEEE.
  • Zhanga, J. , Huang, D.Sh. , Lok, T.M. , R. Lyu, M.(2006).” A novel adaptive sequential niche technique for multimodal function optimization”, Neurocomputing.
  • Ghosh, P. , Zafar, H. , Mandal, A.(2011). “Modified Local Neighborhood Based Niching Particle Swarm Optimization for Multimodal Function Optimization”, Springer-Verlag Berlin: Heidelberg.
  • Rajabioun, R. , Atashpaz-Gargari, E. , Lucas, C. (2008). “Colonial Competitive Algorithm as a Tool for Nash Equilibrium Point Achievement”, Springer , ICCSA, Part II, LNCS 5073, pp. 680–695 , Berlin :Heidelberg .
  • Kienzle, J. , Guelfi, N. , Mustafiz, S. (2010).”Crisis Management Systems A Case Study for Aspect-Oriented Modeling” , Springer, Volume 6210, pp 1-22 , Berlin: Heidelberg.
  • Mani Chandy, K. , Aydemir, B.E. , Karpilovsky, E.M. , Zimmerman, D.M.(2003). “Event-Driven Architectures for Distributed Crisis Management,” 15th IASTED Int’l Conf. Parallel and Distributed Computing and Systems.
  • Shetty R.( 2004). “An Event Driven Single Game Solution For Resource Allocation In A Multi-Crisis Environment” , University of South Florida.
  • Jong, K.A.D.(1975). “An analysis of the behaviour of a class of genetic adaptive systems”. PhD thesis, University of Michigan.
  • Mahfoud, S. (1992). “Crowding and preselection revisited”, in: Parallel Problem Solving from Nature, vol. 2, pp. 27–37.
  • Mengsheol, O. , Goldberg, D.(1999). “Probabilistic crowding: deterministic crowding with probabilistic replacement”, in: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 99, pp. 409–416.
  • Pétrowski, A. (1996). “A clearing procedure as a niching method for genetic algorithms”, in: Proceedings of Third IEEE International Conference on Evolutionary Computation, ICEC’96, IEEE Press, Piscataway, NJ,pp. 798–803.
  • Goldberg, D.E. , Richardson, J. (1987).“Genetic algorithms with sharing for multimodal function optimization”, in: Proceedings of the second International Conference on Genetic Algorithms, pp. 41–49.
  • Miller, B.L. , Shaw, M.J.(1996). “Genetic algorithms with dynamic niche sharing for multimodal function optimization”,in:Evolutionary Computation, pp.786-791, 20-22.
  • Goldberg, D.E. , Wang, L. (1998). “Adaptive niching via coevolutionary sharing”,in: Genetic Algorithm sand Evolution Strategies in Engineering and Computer Science, pp. 21–38.
  • Shir, O.M. , Emmerich, M. , Bäck, T. (2010).“Adaptive niche radii and niche shapes 1024 approaches for niching with the CMA-ES”,in: Evolutionary Computation,pp. 97–126.
  • Harik, G. (1997). “Finding multi-modal solutions using restricted tournament selection”, in: Proceedings of the Sixth International Conference on Genetic Algorithms, ICGA-95, pp. 24–31.
  • Roy, R. , Parmee, I.C.(1996).”Adaptive restricted tournament selection for the identification of multiple sub-optima in a multi-modal function”, in: Selected Papers from AISB Workshop on Evolutionary Computing, Springer-Verlag: London, vol. 1143, pp. 236–256.
  • Yin, X. , Germay, N.(1993).” A fast genetic algorithm with sharing scheme using cluster analysis methods in multi-modal function optimization”, in: Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, pp. 450–457.
  • El Imrani, A. , Bouroumi, A. , Zine El Adidine, H. , Limouri, M. , Essaid, A. (2000). ”A fuzzy clustering-based niching approach to multimodal function optimization”, in: Science Direct, Progress in Evolutionary Computation.
  • Li, J.P. , Balazs, M.E. , Parks, G.T. , Clarkson, P.J.(2002).” A species conserving genetic algorithm for multi-modal function optimization”, in: Evolutionary Computation,Vol.10,No.3,pp. 207–234.
  • Li, J.P. , Wood, A. (2009).“Random search with species conservation for multimodal functions”, in: Proceedings of the Eleventh Conference on Congress on Evolutionary Computation, Trondheim, Norway, pp. 3164–3171.
  • Beasley, D. , Bull, D.R. , Martin, R.R. (1993). ”A sequential niche technique for multimodal function optimization”, vol. 1,No.2,pp. 101–125.
  • Zhanga, J. , Huang, D.Sh. , Lok, T.M. , R. Lyu, M. (2006).“A novel adaptive sequential niche technique for multimodal function optimization”, in:Neurocomputing,vol.1,pp.75-80.
  • Mengshoel, O. , E. Goldberg, D.(2000). “ The Crowding Approach to Niching in Genetic Algorithms”, by the Massachusetts Institute of Technology.
  • Ursem, R.K.(1999). “Multinational evolutionary algorithms”, in: Proceedings of the Congress on Evolutionary Computation, vol. 3, pp. 1633–1640.
  • lin, C.Y. , Wu, W.H.(2002).”Niche Identifcation Techniques in multimodal Genetic search with Sharing Scheme”, in: Advances I Engineering software,vol.33,No.11,pp.779-791.
  • Zhang, J. , et al.(2007). “Multi-sub-swarm particle swarm optimization algorithm for multimodal function optimization,” Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pp. 3215-3220.
  • lung,R.I. , Dumitrescu, D.(2004).’’ROAMING OPTIMATION:a new evolutionary technique for multimodal optimization,in:studia univ,
  • lung, R.I. , Dumitrescu, D.(2005).’’Multimodal optimization by using a new subpopulation model’’,in:Computational Intelligence Reports.
  • Rajabioun, R. , Atashpaz-Gargari, E. , Lucas, C. , Gervasi, O. , Murgante, B. , LaganÃ, A. , Taniar, D. , Mun, Y. , Gavrilova, M. (2008). “Colonial Competitive Algorithm as a Tool for Nash Equilibrium Point Achievement,Computational Science and Its Applications” , Lecture Notes in Computer Science,Vol. 5073, Springer –Berlin: Heidelberg, pp. 680-695.
  • < levine.sscnet.ucla.edu /general /whatis.htm>[ May 2006]
  • Pavlidis, N. G. , Parsopoulos, K. E. , Vrahatis, M. N. (2005). “Computing nash equilibria through computational intelligence methods”. Comput. Appl. Math, pp.113-136.
  • Nash, J.(1951). “Non-cooperative games”. Annals of Mathematics.
  • Webb, J.(1385). “Game Theory: Decisions, Interaction and Evolution” , Springer,pp.85-145.
  • Nash, J. (1950). “Equilibrium Points in n-Person Games”.
  • McKelvey,R. (1991). “A Liapunov function for Nash equilibria”, Technical report.
  • McKelvey,R. , McLennan, A.(1996). “Computation of equilibria in ¯nite games”. In H. M. Amman, D. A. Kendrick, and J. Rust, editors, Handbook of Computational Economics, chapter 2, vol. 1, pp. 87-142. Elsevier.
  • McKelvey, R. , McLennan, A. , Turocy, T.(2000). “Gambit Command Language” , California Institute of Technology.
  • McKelvey, R. , M. McLennan, A. L. Turocy, Th.(2007). “Gambit: Software tools for game theory”. Technical report, Version 0.2007.01.30.
  • Yang, Z., Yong, W. , Cheng,P.(2009). ” Improved Imperialist Competitive Algorithm for Constrained Optimization”. In :Computer Science-Technology and Applications, 2009. IFCSTA ’09. International Forum.
  • Abdechiri, M., Faez, K. Bahrami, H.(2010).  ” Adaptive Imperialist Competitive Algorithm (AICA) ”, in: Cognitive Informatics (ICCI), 2010 9th IEEE International Conference on 2010.

 

  • Bahrami, H., Faez, K.  , Abdechiri, M.(2010).  ” Imperialist Competitive Algorithm Using Chaos Theory for Optimization (CICA) ”. in: Computer Modelling and Simulation (UKSim), 2010 12th International Conference on
  • Coelho, L.D.S., Afonso, L.D. , Alotto, P.(2012). “A Modified Imperialist Competitive Algorithm for Optimization in Electromagnetics Magnetics”, in: IEEE Transactions,p. 579-582.
  • Yang, S.D., Yi, Y.L. , Shan, Z.Y.(2012). ” Gbest-guided Imperialist Competitive Algorithm for Global Numerical Optimization. in Computer Distributed Control and Intelligent Environmental Monitoring (CDCIEM) ”, in: International Conference on. 2012.

 

Reviews

There are no reviews yet.

Be the first to review “Improving The Imperialist Competitive Algorithm To Find Nash Equilibrium Points In Crisis Management Problem”

Related products

SKU: send_b2017_0015_d1182 Category: Tags: , , , , ,