Optimization problems and algorithms

Optimization problems and algorithms

• 1.
  Optimization Problems and Algorithms Dr.Mohammed M. Nasef Mathematics Department, Faculty of Science, Menoufia University Member at Scientific Research Group in Egypt(SERG) Workshop on Intelligent System and Applications (ISA’17) Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 13 May 2017
• 2.
  Overview  Definition ofOptimization  Definition of Optimization Problems  Types of Optimization Techniques  Meta-heuristic Algorithms  An Example : Whale Optimization Algorithm 2 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University.
• 3.
  Definition of Optimization 3 Workshopon Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. The process of finding the best values for the variables of a particular problem to minimize or maximize an objective function
• 4.
  Definition of OptimizationProblem 4 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Optimization Problem Variables Continuous Discrete Constraints Constrained Unconstrained Objective Function Single Multi
• 5.
  Definition of OptimizationProblem (cont.) 5 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 𝐟 𝐱 𝟏, 𝐱𝟐 = 𝐱 𝟏 𝟐 +𝟐𝐱 𝟐 𝟐 -0.3cos(3 𝛑𝐱 𝟏)( 4 𝛑𝐱 𝟐)+0.3 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐦𝐢𝐧(𝐟) 𝐀𝐧 𝐞𝐱𝐚𝐦𝐩𝐥𝐞 ∶ 𝐬𝐢𝐧𝐠𝐥𝐞 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐯𝐚𝐫𝐢𝐚𝐛𝐥𝐞𝐬 ∈ [𝟏𝟎, −𝟏𝟎] 𝐔𝐧𝐜𝐨𝐧𝐬𝐭𝐫𝐚𝐢𝐧𝐞𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦
• 6.
  Definition of OptimizationProblem (cont.) 6 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Min f(z1, z2, z3) = (-100-(z1-5)2 - (z2-5)2 +(z3-5)2)/100 Subject to; h(z1, z2, z3) = (z1 - 3)2 + (z2 - 2)2 + (z3 - 5)2 – 0.0625 ≤ 0 where; 0 ≤ zi ≤ 10; 𝐀𝐧 𝐞𝐱𝐚𝐦𝐩𝐥𝐞 ∶ 𝐬𝐢𝐧𝐠𝐥𝐞 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐂𝐨𝐧𝐬𝐭𝐫𝐚𝐢𝐧𝐞𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦
• 7.
  Definition of OptimizationProblem (cont.) 7 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 𝐀𝐧 𝐞𝐱𝐚𝐦𝐩𝐥𝐞 ∶ 𝐌𝐮𝐥𝐭𝐢 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐔𝐧𝐜𝐨𝐧𝐬𝐭𝐫𝐚𝐢𝐧𝐞𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐦𝐢𝐧(𝐟𝟏 ) & 𝐦𝐢𝐧(𝐟𝟐 ) & 𝐦𝐢𝐧(𝐟𝟑 )
• 8.
  Definition of OptimizationProblem (cont.) 8 Workshop on Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 𝐀𝐧 𝐞𝐱𝐚𝐦𝐩𝐥𝐞 ∶ 𝐌𝐮𝐥𝐭𝐢 𝐨𝐛𝐣𝐞𝐜𝐭𝐢𝐯𝐞 𝐟𝐮𝐧𝐜𝐭𝐢𝐨𝐧 𝐂𝐨𝐧𝐬𝐭𝐫𝐚𝐢𝐧𝐞𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝒎𝒊𝒏 = { 𝐬𝐮𝐛𝐣𝐞𝐜𝐭 𝐭𝐨;
• 9.
  9 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Types of Optimization Techniques Optimization Technique Conventional Mathematical Programming Calculus Methods Network Methods Nonconventional Meta-heuristic algorithms
• 10.
  10 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Meta-heuristic Algorithms Meta-heuristic is a general algorithmic framework which can be applied to different optimization problems with relatively few modifications to make them adapted to a specific problem.
• 11.
  11 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Meta-heuristic Algorithms (cont.) Meta-heuristic algorithms Evolutionary algorithms GA GP Physics-based algorithms CSS SA Swarm-based algorithms Whale Ant Colony Human-based algorithms TLBO EMA Genetic Algorithm (GA) Genetic Programming (GP) Charged System Search (CSS) Simulated Annealing (SA) Teaching Learning Based Optimization(TLBO) Exchange Market Algorithm (EMA)
• 12.
  12 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. An Example : Whale optimization algorithm 1- Encircling prey 2- Bubble-net attacking method (exploitation phase) 3- Search for prey (exploration phase) Behavior of Whale
• 13.
  13 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Whale optimization algorithm(cont.) Mathematical Model Where t is the current iteration, A and C are coefficient vectors, X* is the position vector of the best solution, and X indicates the position vector of a solution, | | is the absolute value. 1- Encircling prey
• 14.
  14 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. Whale optimization algorithm (cont.) Where components of a are linearly decreased from 2 to 0 over the course of iterations and r is random vector in [0; 1] The vectors A and C are calculated as follows: Mathematical Model (cont.)
• 15.
  15 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 2- Bubble-net mechanism (exploitation phase) Whale optimization algorithm (cont.) Mathematical Model (cont.) Where the value of A is a random value in interval [-a, a] and the value of a is decreased from 2 to 0 , D’ =| X*(t) - X(t) | is the distance between the prey (best solution) and the ith whale, b is a constant, l is a random number in [-1; 1], and p is a random number in [0; 1]
• 16.
  16 Workshop on IntelligentSystem and Applications (ISA’17), Faculty of Computers and Informatics, Benha University. 3- search for prey (exploration phase) Whale optimization algorithm (cont.) Mathematical Model (cont.) Where Xrand is a random position vector chosen from the current population. In order to force the search agent to move far a way from reference whale, we use the A with values > 1 or < 1
• 17.
  Thanks and Acknowledgement Workshopon Intelligent System and Applications (ISA’17), Faculty of Computers and Informatics, Benha University.