بهینه سازی (ریاضیاتی) چیست؟ — راهنمای جامع


«بهینه سازی ریاضیاتی» (Mathematical Optimization) که به آن «برنامه‌نویسی ریاضیاتی» (Mathematical Programming) نیز گفته می‌شود، فرایندی است که در آن بهترین جواب (با توجه به مجموعه‌ای از معیارها) از میان مجموعه‌ای از جواب‌های ممکن، برای یک مسأله خاص انتخاب می‌شود. امروزه مسائل بهینه سازی در تمامی رشته‌های علمی کَمی (Quantitative Disciplines) نظیر «علوم کامپیوتر» (Computer Science)، مهندسی (Engineering)، «تحقیق در عملیات» (Operations Research)، «اقتصاد» (Economics) و سایر موارد مورد استفاده قرار می‌گیرند. در طول قرن‌های متمادی، توسعه روش‌های تولید جواب و حل مسأله، یکی از حوزه‌های مهم تحقیقاتی در علم «ریاضیات» (Mathematics) بوده است و اهمیت آن‌ها در طی چند سال گذشته چند برابر شده است.

جهت درک بهتر و اصولی‌تر حوزه بهینه سازی (ریاضیاتی)، ابتدا لازم است تا شناخت کافی در مورد مسائل بهینه سازی ایجاد شود. به بیان ساده، در یک «مسأله بهینه سازی» (Optimization Problems)، هدف «کمینه‌سازی» (Minimizing) یا «بیشینه‌سازی» (Maximizing) یک «تابع حقیقی» (Real Function) است؛ برای چنین کاری سیستم بهینه سازی ریاضیاتی، به طور سیستماتیک، مقادیر ورودی را از یک مجموعه مجاز از مقادیر انتخاب و پس از آن، مقدار تابع حقیقی را محاسبه می‌کند.

تعمیم نظریه بهینه سازی (Optimization Theory) و تکنیک‌های آن به دیگر حوزه‌های علمی و تحقیقاتی مرتبط، در حیطه کاربردهای مهم رشته «ریاضیات کاربردی» (Applied Mathematics) محسوب می‌شود. به طور کلی، اصطلاح بهینه سازی به فرایندی اطلاق می‌شود که هدف آن پیدا کردن بهترین مقادیر یک (یا چند) «تابع هدف» (Objective Functions) در یک دامنه تعریف شده است.

بهینه سازی

مؤلفه‌های یک مدل بهینه سازی

بهینه سازی ابزار مهمی در «تصمیم‌گیری» (Decision Making) و تحلیل سیستم‌های فیزیکی محسوب می‌شود. از نظر ریاضی، یک مسأله بهینه سازی، مسأله پیدا کردن بهترین جواب از میان مجموعه‌ای از جواب‌های کاندید (Candidate) یا امکان‌پذیر (Feasible) است.

بهینه سازی

ساختن یک مدل بهینه سازی

اولین گام در فرایند بهینه سازی، ساختن یک مدل مناسب برای بهینه سازی است؛ مدل‌سازی (Modelling)، به فرایند شناسایی و نمایش ریاضی «هدف» (Objective)، «متغیرها» (Variables) و «قیدهای» (Constraints) مسأله گفته می‌شود:

  • هدف (Objective)، معیار کمی عملکرد سیستم است که قرار است کمینه یا بیشینه شود. به عنوان نمونه، در «تولید» (Manufacturing) هدف کمینه‌سازی هزینه‌های تولید و یا بیشینه‌سازی سود است. در حالی که در برازش داده‌ها (Data Fitting) روی یک مدل، هدف کمینه‌سازی انحراف کل داده‌های مشاهده شده (Observed Data) از داده‌های پیش‌بینی شده (Predicted Data) است.
  • متغیرها (Variables) یا به عبارت دیگر «ناشناخته‌ها» (Unknowns)، مؤلفه‌هایی از مدل بهینه سازی محسوب می‌شوند که قرار است مقادیر مناسبی برای آن‌ها یافت شود. به عنوان نمونه در فرایند تولید، متغیرها می‌توانند پارامترهایی نظیر مقدار منابع مصرف شده و یا زمان صرف شده در هر فعالیت باشد. در حالی که در برازش داده‌ها، متغیرها همان پارامترهای مدل خواهند بود.
  • قیدها (Constraints) توابعی هستند که روابط میان متغیرها (Variables) را نشان می‌دهد و از این طریق، مقادیر مجاز برای متغیرها مشخص می‌شود. به عنوان نمونه در فرایند تولید، مقدار منابع مصرف شده نمی‌تواند از مقدار منابع در دسترس فراتر برود.

مشخص کردن نوع مسأله بهینه سازی

گام دوم در فرایند بهینه سازی، مشخص کردن نوع و یا طبقه‌بندی مسأله‌ای است که قرار است بهینه‌سازی شود. در ادامه و در بخش‌های بعدی، طبقه‌بندی مسائل بهینه سازی ارائه خواهد شد. پس از این مرحله و مشخص شدن نوع مسأله بهینه‌سازی، نیاز است تا بسته به دامنه و نیازهای مسأله، از میان ابزارهای بهینه‌سازی موجود (تجاری و آکادمیک) برای بهینه‌سازی توابع و پیدا کردن جواب‌های بهینه (یا تقریبی از آن‌ها)، ابزاری که بیشترین تطابق را با نیازهای مسأله دارد، انتخاب کرد و آن را در دامنه مورد نظر مورد استفاده قرار داد.

 مسائل بهینه سازی (Optimization Problems)

مسائل بهینه سازی را می‌توان به شکل زیر نمایش داد:

با داشتن: یک تابع به فرم $$f : A rightarrow R$$ که مقادیر را از مجموعه‌ای نظیر $$A$$ (دامنه مسأله) به اعداد حقیقی (Real Numbers) نگاشت می‌کند.

هدف: پیدا کردن عنصری مثل $$X _ 0 in A$$ است، به طوری که شرط $$f ( X _ 0 ) leq f ( X) ;;; f o r ; a l l;; ; X in A$$ (برای مسائل کمینه‌سازی) یا شرط $$f ( X _ 0 ) geq f ( X) ;;; f o r ; a l l;; ; X in A$$ (برای مسائل بیشینه‌سازی) برقرار باشد.

به فرمول‌بندی مسائل به شکل نشان داده شده، نمایش مسأله بهینه سازی یا نمایش مسأله برنامه‌نویسی ریاضی (Mathematical Programming Problem) گفته می‌شود. نکته بسیار مهم در مورد مسائل بهینه‌سازی این است که بسیاری از مسائل «جهان واقعی» (Real-World) و مسائل تئوری را می‌توان از طریق چارچوب عمومی نمایش داده شده مدل‌سازی کرد. به فرمول بندی مسائل بهینه سازی در قالب زیر توجه کنید:

$$f ( X _ 0 ) geq f ( X ) ;;; Leftrightarrow ;;; widetilde f ( X _ 0 ) leq widetilde f ( X )$$

$$widetilde f ( X ) :=- f ( X ) , ;;;;; widetilde f :A rightarrow R$$

با توجه به این که فرمول‌بندی مسائل بهینه سازی در قالب مسائل کمینه‌سازی (فرمول‌بندی بالا)، معتبر (Valid) است، در چنین حالتی حل کردن مسائل کمینه سازی (با استفاده از فرمول‌بندی نمایش داده شده) ساده‌تر خواهد بود. با این حال، فرمول‌بندی مسائل بهینه سازی در قالب مسائل بیشینه‌سازی نیز معتبر خواهد بود.

مفاهیم اولیه در بهینه سازی (ریاضیاتی)

روش‌های بهینه سازی، یکی از معتبرترین و قابل قبول‌ترین روش‌های حل مسأله در حوزه‌‌های مختلف علمی محسوب می‌شوند. به عنوان نمونه، در رشته فیزیک، به مسائلی که از طریق چارچوب بالا فرمول‌بندی شوند، تکنیک‌های «کمینه‌سازی انرژی» (Energy Minimization) گفته می‌شود. به عبارت دیگر در اصل، مقدار تابع $$f$$ انرژی سیستمی که مدل‌سازی شده است را نشان می‌دهد. از جمله سیستم‌های بهینه سازی که از مفاهیم موجود در حوزه فیزیک («فیزیک آماری» (Statistical Physics)) استفاده می‌کنند، می‌تواند به الگوریتم «بهینه سازی اکسترمال» (Extremal Optimization) اشاره کرد. در ادامه، کدهای پیاده‌سازی الگوریتم بهینه سازی اکسترمال در زبان Ruby نمایش داده شده است:

def euc_2d(c1, c2)
  Math.sqrt((c1[0] - c2[0])**2.0 + (c1[1] - c2[1])**2.0).round
end

def cost(permutation, cities)
  distance =0
  permutation.each_with_index do |c1, i|
    c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
    distance += euc_2d(cities[c1], cities[c2])
  end
  return distance
end

def random_permutation(cities)
  perm = Array.new(cities.size) i
  perm.each_index do |i|
    r = rand(perm.size-i) + i
    perm[r], perm[i] = perm[i], perm[r]
  end
  return perm
end

def calculate_neighbor_rank(city_number, cities, ignore=[])
  neighbors = []
  cities.each_with_index do |city, i|
    next if i==city_number or ignore.include?(i)
    neighbor = :number=>i
    neighbor[:distance] = euc_2d(cities[city_number], city)
    neighbors << neighbor
  end
  return neighbors.sort!
end

def get_edges_for_city(city_number, permutation)
  c1, c2 = nil, nil
  permutation.each_with_index do |c, i|
    if c == city_number
      c1 = (i==0) ? permutation.last : permutation[i-1]
      c2 = (i==permutation.size-1) ? permutation.first : permutation[i+1]
      break
    end
  end
  return [c1, c2]
end

def calculate_city_fitness(permutation, city_number, cities)
  c1, c2 = get_edges_for_city(city_number, permutation)
  neighbors = calculate_neighbor_rank(city_number, cities)
  n1, n2 = -1, -1
  neighbors.each_with_index do |neighbor,i|
    n1 = i+1 if neighbor[:number] == c1
    n2 = i+1 if neighbor[:number] == c2
    break if n1!=-1 and n2!=-1
  end
  return 3.0 / (n1.to_f + n2.to_f)
end

def calculate_city_fitnesses(cities, permutation)
  city_fitnesses = []
  cities.each_with_index do |city, i|
    city_fitness = :number=>i
    city_fitness[:fitness] = calculate_city_fitness(permutation, i, cities)
    city_fitnesses << city_fitness
  end
  return city_fitnesses.sort! y[:fitness] <=> x[:fitness]
end

def calculate_component_probabilities(ordered_components, tau)
  sum = 0.0
  ordered_components.each_with_index do |component, i|
    component[:prob] = (i+1.0)**(-tau)
    sum += component[:prob]
  end
  return sum
end

def make_selection(components, sum_probability)
  selection = rand()
  components.each_with_index do |component, i|
    selection -= (component[:prob] / sum_probability)
    return component[:number] if selection <= 0.0
  end
  return components.last[:number]
end

def probabilistic_selection(ordered_components, tau, exclude=[])
  sum = calculate_component_probabilities(ordered_components, tau)
  selected_city = nil
  begin
    selected_city = make_selection(ordered_components, sum)
  end while exclude.include?(selected_city)
  return selected_city
end

def vary_permutation(permutation, selected, new, long_edge)
  perm = Array.new(permutation)
  c1, c2 = perm.rindex(selected), perm.rindex(new)
  p1,p2 = (c1<c2) ? [c1,c2] : [c2,c1]
  right = (c1==perm.size-1) ? 0 : c1+1
  if perm[right] == long_edge
    perm[p1+1..p2] = perm[p1+1..p2].reverse
  else
    perm[p1...p2] = perm[p1...p2].reverse
  end
  return perm
end

def get_long_edge(edges, neighbor_distances)
  n1 = neighbor_distances.find x
  n2 = neighbor_distances.find 
  return (n1[:distance] > n2[:distance]) ? n1[:number] : n2[:number]
end

def create_new_perm(cities, tau, perm)
  city_fitnesses = calculate_city_fitnesses(cities, perm)
  selected_city = probabilistic_selection(city_fitnesses.reverse, tau)
  edges = get_edges_for_city(selected_city, perm)
  neighbors = calculate_neighbor_rank(selected_city, cities)
  new_neighbor = probabilistic_selection(neighbors, tau, edges)
  long_edge = get_long_edge(edges, neighbors)
  return vary_permutation(perm, selected_city, new_neighbor, long_edge)
end

def search(cities, max_iterations, tau)
  current = :vector=>random_permutation(cities)
  current[:cost] = cost(current[:vector], cities)
  best = current
  max_iterations.times do |iter|
    candidate = 
    candidate[:vector] = create_new_perm(cities, tau, current[:vector])
    candidate[:cost] = cost(candidate[:vector], cities)
    current = candidate
    best = candidate if candidate[:cost] < best[:cost]
    puts " > iter #(iter+1), curr=#current[:cost], best=#best[:cost]"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655],
   [880,660],[25,230],[525,1000],[580,1175],[650,1130],[1605,620],
   [1220,580],[1465,200],[1530,5],[845,680],[725,370],[145,665],
   [415,635],[510,875],[560,365],[300,465],[520,585],[480,415],
   [835,625],[975,580],[1215,245],[1320,315],[1250,400],[660,180],
   [410,250],[420,555],[575,665],[1150,1160],[700,580],[685,595],
   [685,610],[770,610],[795,645],[720,635],[760,650],[475,960],
   [95,260],[875,920],[700,500],[555,815],[830,485],[1170,65],
   [830,610],[605,625],[595,360],[1340,725],[1740,245]]
  # algorithm configuration
  max_iterations = 250
  tau = 1.8
  # execute the algorithm
  best = search(berlin52, max_iterations, tau)
  puts "Done. Best Solution: c=#best[:cost], v=#best[:vector].inspect"
end

همچنین در حوزه «هوش مصنوعی» (Artificial Intelligence) و «یادگیری ماشین» (Machine Learning) نیز بسیار حیاتی است که کیفیت «مدل داده» (Data Model)، به طور پیوسته و توسط یک «تابع هزینه» (Cost Function) ارزیابی شود؛ در این حالت، منظور از کمینه‌سازی تابع هزینه، پیدا کردن مجموعه‌ای از «پارامترهای بهینه» (Optimal Parameters) است که سبب تولید مقدار بهینه خطا (کمترین خطای ممکن) در سیستم می‌شوند.

از جمله الگوریتم‌های بهینه سازی که در دسته «الگوریتم‌های تخمین توزیع» (Estimation of Distribution Algorithms) قرار می‌گیرد، می‌توان به الگوریتم «بهینه سازی بیزی» (Bayesian Optimization) اشاره کرد. در ادامه، کدهای پیاده‌سازی الگوریتم بهینه سازی بیزی در زبان Ruby نمایش داده شده است:

def onemax(vector)
  return vector.inject(0)
end

def random_bitstring(size)
  return Array.new(size) ((rand()<0.5) ? 1 : 0) 
end

def path_exists?(i, j, graph)
  visited, stack = [], [i]
  while !stack.empty?
    return true if stack.include?(j)
    k = stack.shift
    next if visited.include?(k)
    visited << k
    graph[k][:out].each 
  end
  return false
end

def can_add_edge?(i, j, graph)
  return !graph[i][:out].include?(j) && !path_exists?(j, i, graph)
end

def get_viable_parents(node, graph)
  viable = []
  graph.size.times do |i|
    if node!=i and can_add_edge?(node, i, graph)
      viable << i
    end
  end
  return viable
end

def compute_count_for_edges(pop, indexes)
  counts = Array.new(2**(indexes.size))0
  pop.each do |p|
    index = 0
    indexes.reverse.each_with_index do |v,i|
      index += ((p[:bitstring][v] == 1) ? 1 : 0) * (2**i)
    end
    counts[index] += 1
  end
 return counts
end

def fact(v)
  return v <= 1 ? 1 : v*fact(v-1)
end

def k2equation(node, candidates, pop)
  counts = compute_count_for_edges(pop, [node]+candidates)
  total = nil
  (counts.size/2).times do |i|
    a1, a2 = counts[i*2], counts[(i*2)+1]
    rs = (1.0/fact((a1+a2)+1).to_f) * fact(a1).to_f * fact(a2).to_f
    total = (total.nil? ? rs : total*rs)
  end
  return total
end

def compute_gains(node, graph, pop, max=2)
  viable = get_viable_parents(node[:num], graph)
  gains = Array.new(graph.size) -1.0
  gains.each_index do |i|
    if graph[i][:in].size < max and viable.include?(i)
      gains[i] = k2equation(node[:num], node[:in]+[i], pop)
    end
  end
  return gains
end

def construct_network(pop, prob_size, max_edges=3*pop.size)
  graph = Array.new(prob_size) i
  gains = Array.new(prob_size)
  max_edges.times do
    max, from, to = -1, nil, nil
    graph.each_with_index do |node, i|
      gains[i] = compute_gains(node, graph, pop)
      gains[i].each_with_index  from,to,max = i,j,v if v>max
    end
    break if max <= 0.0
    graph[from][:out] << to
    graph[to][:in] << from
  end
  return graph
end

def topological_ordering(graph)
  graph.each 
  ordered,stack = [], graph.select 
  while ordered.size < graph.size
    current = stack.shift
    current[:out].each do |edge|
      node = graph.find 
      node[:count] -= 1
      stack << node if node[:count] <= 0
    end
    ordered << current
  end
  return ordered
end

def marginal_probability(i, pop)
  return pop.inject(0.0) s + x[:bitstring][i] / pop.size.to_f
end

def calculate_probability(node, bitstring, graph, pop)
  return marginal_probability(node[:num], pop) if node[:in].empty?
  counts = compute_count_for_edges(pop, [node[:num]]+node[:in])
  index = 0
  node[:in].reverse.each_with_index do |v,i|
    index += ((bitstring[v] == 1) ? 1 : 0) * (2**i)
  end
  i1 = index + (1*2**(node[:in].size))
  i2 = index + (0*2**(node[:in].size))
  a1, a2 = counts[i1].to_f, counts[i2].to_f
  return a1/(a1+a2)
end

def probabilistic_logic_sample(graph, pop)
  bitstring = Array.new(graph.size)
  graph.each do |node|
    prob = calculate_probability(node, bitstring, graph, pop)
    bitstring[node[:num]] = ((rand() < prob) ? 1 : 0)
  end
  return :bitstring=>bitstring
end

def sample_from_network(pop, graph, num_samples)
  ordered = topological_ordering(graph)
  samples = Array.new(num_samples) do
    probabilistic_logic_sample(ordered, pop)
  end
  return samples
end

def search(num_bits, max_iter, pop_size, select_size, num_children)
  pop = Array.new(pop_size)  :bitstring=>random_bitstring(num_bits) 
  pop.each
  best = pop.sort!.first
  max_iter.times do |it|
    selected = pop.first(select_size)
    network = construct_network(selected, num_bits)
    arcs = network.inject(0)
    children = sample_from_network(selected, network, num_children)
    children.each
    children.each 
    pop = pop[0...(pop_size-select_size)] + children
    pop.sort! 
    best = pop.first if pop.first[:cost] >= best[:cost]
    puts " >it=#it, arcs=#arcs, f=#best[:cost], [#best[:bitstring]]"
    converged = pop.select  x[:bitstring]!=pop.first[:bitstring].empty?
    break if converged or best[:cost]==num_bits
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  num_bits = 20
  # algorithm configuration
  max_iter = 100
  pop_size = 50
  select_size = 15
  num_children = 25
  # execute the algorithm
  best = search(num_bits, max_iter, pop_size, select_size, num_children)
  puts "done! Solution: f=#best[:cost]/#num_bits, s=#best[:bitstring]"
end

در فرمول‌بندی مسائل بهینه سازی (Optimization Problems)، مجموعه $$A$$ زیر مجموعه‌ای از «فضای اقلیدسی» (Euclidean Space) یا $$R ^ n $$ است. معمولا در مسائل بهینه سازی، برای $$A$$ مجموعه‌ای از «قیود» (Constraints) تعریف می‌شوند؛ قیود، «برابری‌ها» (Equalities) یا «نابرابری‌هایی» (Inequalities) هستند که تمامی اعضای مجموعه $$A$$ باید آن‌ها را ارضا کنند. همچنین، به مجموعه $$A$$ یا همان دامنه یک تابع بهینه‌سازی مانند $$f$$ (به عبارت دیگر، دامنه تابع هدف مسأله بهینه‌سازی)، «فضای جستجو» (Search Space) یا «مجموعه انتخاب» (Choice Set) نیز گفته می‌شود.

با توجه به تعاریف انجام شده، هر یک از اعضای مجموعه $$A$$، یک جواب کاندید یا جواب امکان‌پذیر برای تابع بهینه‌سازی $$f$$ محسوب می‌شوند. تابع بهینه‌سازی $$f$$ با نام‌های دیگری نظیر «تابع هدف» (Object Function)، «تابع زیان» (Loss Function) یا «تابع هزینه» (Loss Function)، «تابع برازندگی» (Fitness Function) و در برخی رشته‌های خاص، «تابع انرژی» (Energy Function) شناخته می‌شود. تابع زیان و تابع هزینه برای مسائل کمینه‌سازی و تابع هدف، برای مسائل بیشینه‌سازی مورد استفاده قرار می‌گیرند.

به یک جواب کاندید یا امکان‌پذیر، که تابع هدف مسأله بهینه سازی را بیشینه یا کمینه کند، «جواب بهینه» (Optimal Solution) گفته می‌شود. همانطور که پیش از این نیز اشاره شد، مسائل بهینه سازی در ریاضیات، معمولا در قالب مسائل «کمینه‌سازی» (Minimization) نمایش داده می‌شوند.

کمینه محلی (Local Minimum)، بیشینه محلی (Local Maximum) و بهینه سراسری (Global Optimum)

یک کمینه محلی $$X^star$$ تابع $$f$$، عنصری است که به ازاء آن پارامتری مانند $$delta > 0$$ وجود دارد، به طوری که:

,$$forall X in A ; w h e r e parallel X – X ^ star parallel leq delta$$

و به ازاء تمامی مقادیر $$X$$ که قید (Constraint) بالا را ارضا می‌کنند، عبارت $$f ( X ^ star ) leq f ( X )$$ برقرار است. به عبارت دیگر در برخی نواحی اطراف $$X^star$$، تمامی مقادیر تابع $$f$$، بزرگتر یا برابر با مقدار عنصر کمینه محلی هستند. همچنین، بیشینه محلی به صورت مشابه و به شکل زیر تعریف می‌شود:

یک بیشینه محلی $$X^star$$ تابع $$f$$، عنصری است که به ازاء آن پارامتری مانند $$delta > 0$$ وجود دارد، به طوری که:

,$$forall X in A ; w h e r e parallel X – X ^ star parallel leq delta$$

و به ازاء تمامی مقادیر $$X$$ که قید (Constraint) بالا را ارضا می‌کنند، عبارت $$f ( X ^ star ) geq f ( X )$$ برقرار است. به عبارت دیگر در برخی نواحی اطراف $$X^star$$، تمامی مقادیر تابع $$f$$، کوچکتر یا برابر با مقدار عنصر بیشینه محلی هستند.

بهینه سازی محدب و غیر محدب

اگرچه عناصر کمینه یا بیشینه محلی بهتر از (یا حداقل برابر با) عناصر همسایگی اطرافشان هستند، ولی یک عنصر بیشینه یا کمینه سراسری (یا همان مقدار بهینه سراسری (Global Optimum)) از تمامی جواب‌های کاندید یا امکان‌پذیر برای یک مسأله بهینه سازی بهتر خواهد بود. به طور کلی، تنها در صورتی که تابع هدف مسأله بهینه سازی «محدب» (Convex) نباشد، ممکن است بیش از یک «کمینه محلی» (Local Minimum) یا «بیشینه محلی» (Local maximum) در مسأله وجود داشته باشد.

در مسائل «بهینه سازی محدب» (Convex Optimization)، در صورتی که یک جواب بیشینه محلی یا کمینه محلی برای مسأله وجود داشته باشد، این جواب، بهینه سراسری مسأله مورد نظر نیز خواهد بود. با این حال، در یک مسأله بهینه سازی «غیر محدب» (Non-Convex) ممکن است بیش از یک جواب بیشینه محلی یا کمینه محلی وجود داشته باشد که لزوما همه آن‌ها بهینه سراسری مسأله مورد نظر نخواهند بود.

بهینه سازی

بسیاری از الگوریتم‌هایی که برای حل مسائل بهینه سازی غیر محدب پیشنهاد شده‌اند (از جمله بسیاری از الگوریتم‌های تجاری تولید شده برای حل مسائل بهینه سازی غیر محدب)، به خوبی قادر نیستند میان جواب‌های بهینه محلی (بیشینه محلی یا کمینه محلی) و جواب‌های بهینه سراسری (بیشینه سراسری یا کمینه سراسری) تمایز قائل شوند و تمامی جواب‌های بهینه محلی یافت شده را به عنوان جواب واقعی مسأله بهینه سازی مورد نظر به شمار می‌آورند.

بهینه سازی

برای غلبه بر چنین معضلی در روش‌های بهینه سازی، زیر شاخه‌ای به نام «بهینه سازی سراسری» (Global Optimization) در حوزه‌های ریاضیات کاربردی و «آنالیز عددی» (Numerical Analysis) پدید آمده است. هدف روش‌های بهینه سازی سراسری، پیاده‌سازی «الگوریتم‌های قطعی» (Deterministic Algorithms) است که قادر هستند «همگرایی» (Convergence) به جواب بهینه سراسری واقعی یک مسئله بهینه سازی محدب را در زمان محدود تضمین کنند.

بهینه سازی

نمادگذاری‌ها در بهینه سازی ریاضیاتی

در ادامه، مهم‌ترین نماد‌گذاری‌ها در بهینه سازی ریاضیاتی مورد بررسی قرار می‌گیرند.

مقدار کمینه یا بیشینه یک تابع

نمادگذاری زیر را در نظر بگیرید:

$$m i n _ x in R ( x ^ 2 + 1 )$$

نمادگذاری نمایش داده شده، مقدار کمینه تابع هدف $$ x ^ 2 + 1$$ را، وقتی که مقدار $$x$$ از مجموعه اعداد حقیقی $$R$$ انتخاب شده باشد، نمایش می‌دهد. مقدار کمینه این تابع برابر با 1 (یک) است و در نقطه $$x=0$$ رخ می‌دهد. به طور مشابه، نمادگذاری زیر:

$$m a x _ x in R ; (2 x)$$

مقدار بیشینه تابع هدف $$(2 x)$$ را نمایش می‌دهد. در این تابع، پارامتر $$x$$ می‌تواند هر مقدار حقیقی به خود بگیرد. در این حالت، از آنجایی که تابع هدف «بی‌کران» (Unbounded) است، هیچ مقدار بیشینه‌ای برای آن وجود نخواهد داشت. به عبارت دیگر، جواب این مسأله «بی‌نهایت» (Infinity) یا «تعریف نشده» (Undefined) است.

آرگومان‌های ورودی بهینه (Optimal Input Argument)

نمادگذاری زیر را در نظر بگیرید:

$$ a r g ;m i n _ x in left ( -infty , -1 right] ( x ^ 2 + 1 )$$

نمادگذاری که در ادامه مشاهده خواهید کرد، هیچ تفاوتی با نمادگذاری بالا ندارد:

$$ a r g ;m i n _ x ( x ^ 2 + 1 ), ; s u b j e c t ; to: x in left ( -infty , -1 right] $$

نمادگذاری‌های نمایش داده شده، مقدار (یا مقادیر) آرگومان $$x$$ در بازه $$x in left ( -infty , -1 right]$$ را نشان می‌دهد؛ مقادیری که تابع هدف $$x ^ 2 + 1$$ را کمینه‌سازی می‌کنند. نکته مهم در مورد نمادگذاری تعریف شده برای مسأله بهینه‌سازی بالا این است که در این نمادگذاری، مقادیر کمینه تابع هدف مشخص نشده‌اند و تنها قید مرتبط با مقادیر ممکن برای آرگومان $$x$$ نمایش داده شده است. در این مورد، از آنجایی که مقدار صفر در مجموعه مقادیر امکان‌پذیر آرگومان $$x$$ وجود ندارد، مقدار کمینه این تابع در نقطه $$x=-1$$ حاصل می‌شود.

به طور مشابه، برای نمایش آرگومان‌های ورودی بهینه یک مسأله بیشینه‌سازی، نمادگذاری زیر را در نظر بگیرید:

$$ a r g ;m a x _ x in left [ -5 , 5 right],; yin R ( x ;cos ;y )$$

مانند حالت قبل، نمادگذاری که در ادامه مشاهده خواهید کرد، هیچ تفاوتی با نمادگذاری بالا ندارد:

$$ a r g ;m a x _ x , ;y ( x ; cos ;y), ; s u b j e c t; t o : x in left [ -5 , 5 right],; yin R$$

نمادگذاری‌های نمایش داده شده، جفت مقادیر $$(x,y)$$ را نشان می‌دهند که مقدار تابع هدف $$x ; cos ;y$$ را بیشینه می‌کنند؛ در این تابع هدف، قید خاصی روی آرگومان $$x$$ تعریف شده است که بر اساس آن، تنها مقادیر موجود در بازه $$left [ -5 , 5 right]$$ قابل قبول هستند. مانند مورد قبلی، در نمادگذاری تعریف شده برای مسأله بیشینه‌سازی بالا، مقادیر بیشینه تابع هدف مشخص نشده‌اند و تنها قیدهای مرتبط با مقادیر ممکن برای آرگومان $$x$$ و $$y$$ نمایش داده شده‌اند. در این مورد، جفت مقادیر $$(x,y)$$ که به فرم $$ (5 , ; 2kpi)$$ و $$ (-5 , ; (2 k + 1 ) pi)$$ هستند، جواب‌های این مسأله بهینه‌سازی هستند؛ پارامتر $$k$$ می‌تواند هر مقدار صحیحی را به خود بگیرد.

بنابراین، عملگرهای $$ a r g ;m i n$$ و $$ a r g ;m a x$$، به ترتیب بیانگر «آرگومان کمینه تابع هدف» (Argument of Minimum) و «آرگومان بیشینه تابع هدف» (Argument of Maximum) هستند و مشخص می‌کنند که مسأله مورد نظر، یک مسأله کمینه‌سازی است یا یک مسأله بیشینه‌سازی.

انواع مسائل بهینه سازی

همانطور که پیش از این نیز اشاره شد، گام دوم در فرایند بهینه سازی، مشخص کردن نوع و یا طبقه‌بندی مسأله‌ای است که قرار است بهینه‌سازی شود. از آنجایی که هر یک از الگوریتم‌های حل مسائل بهینه سازی (Optimization)، جهت یافتن مقادیر بهینه انواع خاصی از مسائل پیاده‌سازی می‌شوند، مشخص کردن «دسته‌بندی» (Classification) مدل‌های بهینه سازی نقش مهمی در این فرایند ایفا خواهد کرد. در ادامه، برخی از مهم‌ترین دسته‌بندی‌های ارائه شده از مدل‌های بهینه سازی نمایش داده خواهد شد.

مسائل بهینه سازی «پیوسته» (Continuous) و بهینه سازی «گسسته» (Discrete)

برخی از مدل‌های بهینه سازی، جهت بهینه سازی توابعی طراحی شده‌اند که متغیرهای آن‌ها، مقادیر مجاز خود را از یک «مجموعه گسسته» (Discrete Set) اتخاذ می‌کنند (زیر مجموعه‌ای از مقادیر صحیح)، در حالی که مدل‌های دیگر، برای بهینه سازی توابعی پیاده‌سازی شده‌اند که متغیرهای آن‌ها می‌توانند مقادیر حقیقی (Real Values) به خود بگیرند. به مدل‌هایی که از متغیرهای گسسته استفاده می‌کنند، مدل‌های مسائل بهینه سازی گسسته (Discrete Optimization Problems) و به مدل‌هایی که برای بهینه سازی متغیرهای پیوسته مورد استفاده قرار می‌گیرند، مدل‌های مسائل بهینه سازی پیوسته (Continuous Optimization Problems) گفته می‌شود.

حل کردن مسائل بهینه سازی پیوسته معمولا سخت‌تر از حل مسائل بهینه‌سازی گسسته است؛ از آنجایی که سطح توابع پیوسته هموار (Smooth) هستند، این امکان وجود دارد که از توابع هدف و قیدهای تعریف شده برای مقادیر متغیرها در نقطه $$X$$، جهت استنتاج اطلاعات مرتبط با نقاط موجود در همسایگی این نقطه استفاده کرد و از این طریق، مقادیر بهینه مسأله بهینه سازی پیوسته را پیدا کرد.

با این حال، پیشرفت‌های حاصل شده در توسعه الگوریتم‌های بهینه سازی گسسته و افزایش قابل توجه قدرت محاسباتی سیستم‌های کامپیوتری در چند سال اخیر سبب شده است تا الگوریتم‌هایی توسعه یابند که قادر هستند مسائل بهینه سازی گسسته بزرگ و پیچیده را به شکل بسیار کارآمدی حل کنند.

نکته مهم در مورد این دسته از مدل‌های بهینه سازی این است که مدل‌های پیوسته نقش مهمی در پیاده‌سازی مدل‌های بهینه سازی گسسته دارند. زیرا، بسیاری از مدل‌های بهینه‌سازی گسسته، مسائل بهینه سازی را به دنباله‌ای از زیر مسائل پیوسته (Continuous Subproblems) تقسیم‌بندی می‌کنند و برای حل کردن هر یک از این زیر مسائل، از مدل های بهینه سازی پیوسته استفاده می‌شود. بنابراین، یکی از مؤلفه‌های اساسی مدل‌های بهینه سازی گسسته، روش‌های حل مسائل بهینه‌سازی پیوسته هستند.

یکی از الگوریتم‌هایی که برای بهینه سازی مسائل پیوسته مورد استفاده قرار می‌گیرد، «الگوریتم بهینه‌سازی فاخته» (Cuckoo Optimization Algorithm) نام دارد. در ادامه، کدهای پیاده سازم این الگوریتم در زبان متلب نمایش داده شده است.

clc, clear, close all
%% Set problem parameters
% select your cost function:
costFunction = 'rastrigin';           % F6 +/-5.12
npar  = 100;          % number of optimization variables
varLo = -5;         % Lower  band of parameter
varHi =  5;         % Higher band of parameter
%% Set COA parameters
numCuckooS = 5;             % number of initial population
minNumberOfEggs = 2;        % minimum number of eggs for each cuckoo
maxNumberOfEggs = 4;        % maximum number of eggs for each cuckoo
maxIter = 100;              % maximum iterations of the Cuckoo Algorithm
knnClusterNum = 1;          % number of clusters that we want to make
motionCoeff = 9;            % Lambda variable in COA paper, default=2
accuracy = -inf;           % How much accuracy in answer is needed
maxNumOfCuckoos = 10;      % maximum number of cuckoos that can live at the same time
radiusCoeff = 5;           % Control parameter of egg laying
cuckooPopVariance = 1e-13;   % population variance that cuts the optimization
%% initialize population:
cuckooPop = cell(numCuckooS,1);
% initialize egg laying center for each cuckoo
for cuckooNumber = 1:numCuckooS    
    cuckooPopcuckooNumber.center = ( varHi-varLo )*rand(1,npar) + varLo;
end
%% initialize COA cost minimization plot
figure(1)
hold on
xlabel 'Cuckoo iteration'
ylabel 'Cost Value'
%% Start Cuckoo Optimization Algorithm
iteration = 0;
maxProfit = -1e20;        % Let initial value be negative number
goalPoint = (varHi - varLo)*rand(1,npar) + varLo; % a random goalpoint to start COA
globalBestCuckoo = goalPoint;
globalMaxProfit = maxProfit;
profitVector = [];
while ( (iteration <= maxIter) && (-maxProfit > accuracy) )
    
    iteration = iteration + 1
    
    % initialize number of eggs for each cuckoo
    for cuckooNumber = 1:numCuckooS        
        cuckooPopcuckooNumber.numberOfEggs = floor( (maxNumberOfEggs - minNumberOfEggs) * rand + minNumberOfEggs );
    end
    % get total number of available eggs between all cuckooS
    summ = 0;
    for cuckooNumber = 1:numCuckooS
        summ = summ + cuckooPopcuckooNumber.numberOfEggs;
    end
    % calculate egg laying radius for each Cuckoo, considering problem
    % limitations and ratio of each cuckoo's eggs
    for cuckooNumber = 1:numCuckooS
        cuckooPopcuckooNumber.eggLayingRadius = cuckooPopcuckooNumber.numberOfEggs/summ * ( radiusCoeff * (varHi-varLo) );
    end
    % To lay eggs, we produced some radius values less than egg laying
    % radius of each cuckoo
    for cuckooNumber = 1:numCuckooS
        cuckooPopcuckooNumber.eggLayingRadiuses = cuckooPopcuckooNumber.eggLayingRadius * rand(cuckooPopcuckooNumber.numberOfEggs,1);
    end
    
    for cuckooNumber = 1:numCuckooS
        params = cuckooPopcuckooNumber.center;        % get center values
        tmpRadiuses = cuckooPopcuckooNumber.eggLayingRadiuses;
        numRadiuses = numel(tmpRadiuses);
        % divide a (hyper)circle to 'numRadiuses' segments
        % This is to search all over the current habitat
        angles = linspace(0,2*pi,numRadiuses);    % in Radians
        newParams = [];
        for cnt = 1:numRadiuses
            addingValue = zeros(1,npar);
            for iii = 1:npar
                randNum = floor(2*rand)+1;
                addingValue(iii) = (-1)^randNum * tmpRadiuses(cnt)*cos(angles(cnt)) + tmpRadiuses(cnt)*sin(angles(cnt));
            end
            newParams = [newParams; params +  addingValue ];
        end
        
        
        % check for variable limits
        newParams(find(newParams>varHi)) = varHi;
        newParams(find(newParams<varLo)) = varLo;
        cuckooPopcuckooNumber.newPosition4Egg = newParams;
    end
    
    % Now egg laying is done
    
    % Now that egg positions are found, they are laid, and so its time to
    % remove the eggs on the same positions (because each egg only can go to one nest)
    for cuckooNumber = 1:numCuckooS
        tmpPopulation = cuckooPopcuckooNumber.newPosition4Egg;
        tmpPopulation = floor(tmpPopulation * 1e20)/1e20;
        ii = 2;
        cntt = 1;
        while ii <= size(tmpPopulation,1) || cntt <= size(tmpPopulation,1)
            if all((tmpPopulation(cntt,:) == tmpPopulation(ii,:)))
                tmpPopulation(ii,:) = [];
            end
            ii = ii + 1;
            if ii > size(tmpPopulation,1) && cntt <= size(tmpPopulation,1)
                cntt = cntt + 1;
                ii = cntt + 1;
                if ii > size(tmpPopulation,1)
                    break
                end
            end
        end
        cuckooPopcuckooNumber.newPosition4Egg = tmpPopulation;
    end    
    
     
    % Now we evalute egg positions
    for cuckooNumber = 1:numCuckooS
        cuckooPopcuckooNumber.profitValues = -feval(costFunction,[cuckooPopcuckooNumber.center ; cuckooPopcuckooNumber.newPosition4Egg]);        
    end
    
    % Now we check to see if cuckoo population is more than maxNumOfCuckoos
    % this case we should keep 1st maxNumOfCuckoos cuckoos and kill the others
    allPositions = [];
    whichCuckooPopTheEggBelongs = [];
    tmpProfits = [];
    if numCuckooS > maxNumOfCuckoos
        for cuckooNumber = 1:numCuckooS
            tmpProfits = [tmpProfits; cuckooPopcuckooNumber.profitValues];
            allPositions = [allPositions; [cuckooPopcuckooNumber.center; cuckooPopcuckooNumber.newPosition4Egg(:,1:npar)]];
            whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPopcuckooNumber.newPosition4Egg(:,1:npar),1),1) ];
        end
        % now we sort cuckoo profits
        [sortedProfits, sortingIndex] = sort(tmpProfits,'descend');
        % Get best cuckoo to be copied to next generation
        bestCuckooCenter = allPositions(sortingIndex(1),1:npar);
        
        sortedProfits = sortedProfits(1:maxNumOfCuckoos);
        allPositions = allPositions(sortingIndex(1:maxNumOfCuckoos),:);
        clear cuckooPop
        for ii = 1:maxNumOfCuckoos
            cuckooPopii.newPosition4Egg = allPositions(ii,:);
            cuckooPopii.center = allPositions(ii,:);
            cuckooPopii.profitValues = sortedProfits(ii);
        end
        numCuckooS = maxNumOfCuckoos;
    else
        for cuckooNumber = 1:numCuckooS
            tmpProfits = [tmpProfits; cuckooPopcuckooNumber.profitValues];
            allPositions = [allPositions; [cuckooPopcuckooNumber.center; cuckooPopcuckooNumber.newPosition4Egg(:,1:npar)] ];
            whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPopcuckooNumber.newPosition4Egg(:,1:npar),1),1) ];
        end
        [sortedProfits, sortingIndex] = sort(tmpProfits,'descend');
        % Get best cuckoo to be copied to next generation
        bestCuckooCenter = allPositions(sortingIndex(1),1:npar);
    end
    
    maxProfit  = sortedProfits(1);
    currentBestCuckoo = bestCuckooCenter;
    currentMaxProfit = -feval(costFunction,currentBestCuckoo);
    if currentMaxProfit > globalMaxProfit
        globalBestCuckoo = currentBestCuckoo;
        globalMaxProfit = currentMaxProfit;
    end
    
    % Update cost minimization plot
    plot(iteration, -globalMaxProfit,'ks','linewidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g','MarkerSize',10)
    title([ 'Curent Cost = ' num2str(-globalMaxProfit) ' , at Iteration = ' num2str(iteration) ])
    pause(0.01)
    
    profitVector = [profitVector globalMaxProfit];
    
    % ======== now we have some eggs that are safe and will grow up ==========
    %========= mating: =============
    % first we put all egg positions under each other
    allPositions = [];
    whichCuckooPopTheEggBelongs = [];
    for cuckooNumber = 1:numCuckooS
        allPositions = [allPositions; cuckooPopcuckooNumber.newPosition4Egg(:,1:npar)];
        whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPopcuckooNumber.newPosition4Egg(:,1:npar),1),1) ];
    end
    if sum(var(allPositions)) < cuckooPopVariance
        break
    else
        [clusterNumbers, clusterCenters] = kmeans(allPositions,knnClusterNum);
    end
    % make newly made clusters
    cluster = cell(knnClusterNum,1);
    for ii = 1:knnClusterNum
        clusterii.positions = [];
        clusterii.profits = [];
    end
    
    pointer = zeros(numel(cuckooPop),1);
    for tmpCounter = 1:numel(cuckooPop)
        nEggs = size(cuckooPoptmpCounter.newPosition4Egg,1);
        pointer(tmpCounter) = nEggs;
    end
    for cnt = 1:length(clusterNumbers)
        clusterclusterNumbers(cnt).positions = [clusterclusterNumbers(cnt).positions; cuckooPopwhichCuckooPopTheEggBelongs(cnt).newPosition4Egg(end-pointer(whichCuckooPopTheEggBelongs(cnt))+1,1:npar)];
        clusterclusterNumbers(cnt).profits   = [clusterclusterNumbers(cnt).profits; cuckooPopwhichCuckooPopTheEggBelongs(cnt).profitValues(end-pointer(whichCuckooPopTheEggBelongs(cnt))+1)];
        pointer(whichCuckooPopTheEggBelongs(cnt)) = pointer(whichCuckooPopTheEggBelongs(cnt)) - 1;
    end
    
    % Determine the best cluster
    f_mean = zeros(knnClusterNum,1);
    for cnt = 1:knnClusterNum
        f_mean(cnt) = mean(clustercnt.profits);
    end
    [sorted_f_mean, sortingIndex_f_mean] = sort(f_mean,'descend');
    maxFmean = sorted_f_mean(1);   indexOfBestCluster = sortingIndex_f_mean(1);
    
    % now that we know group with number 'indexOfBestCluster' is the best we 
    % should select their best point az Goal Point of other groups
    [maxProfitInBestCluster, indexOfBestEggPosition] = max(clusterindexOfBestCluster.profits);
    goalPoint  = clusterindexOfBestCluster.positions(indexOfBestEggPosition,1:npar);
    
    % now all other mature Cuckoos must go toward this goal point for laying
    % their eggs
    numNewCuckooS = 0;
    for cntClstr = 1:size(cluster,1)
        tmpCluster = clustercntClstr;
        tmpPositions = tmpCluster.positions;
        for cntPosition = 1:size(tmpPositions,1)
            tmpPositions(cntPosition,:) = tmpPositions(cntPosition,:) + ...
                                          motionCoeff * rand(1,npar) .*  (goalPoint  - tmpPositions(cntPosition,:));
        end
        % check if variables are in range
        tmpPositions(find( tmpPositions>varHi )) = varHi;
        tmpPositions(find( tmpPositions<varLo )) = varLo;
        % update cluster positions
        clustercntClstr.positions = tmpPositions;
        clustercntClstr.center = mean(tmpPositions);
        % update number of cuckoos: numCuckooS
        numNewCuckooS = numNewCuckooS + size(clustercntClstr.positions,1);
    end
    numCuckooS = numNewCuckooS;
    % update cuckooPop
    clear cuckooPop
    cuckooPop = cell(numCuckooS,1);
    cntNumCuckooS = 1;
    for cnt = 1:size(cluster,1)
        tmpCluster = clustercnt;
        tmpPositions = tmpCluster.positions;
        for cntPosition = 1:size(tmpPositions,1)
            cuckooPopcntNumCuckooS.center = clustercnt.positions(cntPosition,1:npar);
            cntNumCuckooS = cntNumCuckooS + 1;
        end
    end
    % Copy the Best cuckoo and its randomized form of this population to go 
    % to the next generation
    currentBestCuckoo = bestCuckooCenter;
    currentMaxProfit = -feval(costFunction,currentBestCuckoo);
    if currentMaxProfit > globalMaxProfit
        globalBestCuckoo = currentBestCuckoo;
        globalMaxProfit = currentMaxProfit;
    end
    cuckooPopend.center = globalBestCuckoo; % This is because the best cuckoo will live longer and won't die right after egg laying
    cuckooPopend.profitValues = -feval(costFunction,cuckooPopend.center);
    tmp = rand(1,npar).*globalBestCuckoo;
    tmp(find( tmp>varHi )) = varHi;
    tmp(find( tmp<varLo )) = varLo;
    cuckooPopend-1.center = tmp;
    cuckooPopend-1.profitValues = -feval(costFunction,cuckooPopend-1.center);
    
end     % end of while
%% Now Algorithm has stopped
disp('Best Params = ')
disp(globalBestCuckoo')
fprintf('n')
disp('Cost = ')
disp(-globalMaxProfit)
% profit history is in:  profitVector
costVector = - profitVector;
figure
plot(costVector,'-ks','linewidth',3,'MarkerEdgeColor','k','MarkerFaceColor','g','MarkerSize',15)
xlabel 'Cuckoo Iteration'
ylabel 'Cost Value'
title(['Current Cost = ' num2str(costVector(end)) ', at iteration = ' num2str(iteration) ])

تابع هدف Rastrigin:

function y = rastrigin(x)
y = 10.0 * size(x,2) + sum(x .^2 - 10.0 * cos(2 * pi .* x),2);

مسائل بهینه سازی «مقید» (Constrained) و بهینه سازی «نامقید» (Unconstrained)

از یک جهت دیگر نیز می‌توان میان مسائل و مدل‌های بهینه سازی قائل شد: مسائلی که هیچ قیدی روی متغیرها تعریف نمی‌کنند و مسائلی که برای متغیرها قید تعریف می‌‌کنند. درصد قابل توجه از مسائلی که در جهان واقعی با آن‌ها سروکار داریم، از نوع مسائل بهینه سازی نامقید هستند. در چند سال اخیر، مطالعات زیادی برای فرمول‌بندی دوباره (Re-Formulation) مسائل بهینه سازی نامقید در قالب مسائل بهینه سازی مقید ارائه شده است. در این مطالعات، از طریق جایگزین کردن قیدهای مسأله با «عبارات جریمه» (Penalty Terms)، یک مسأله بهینه سازی مقید به یک مسأله بهینه سازی نامقید تبدیل می‌شود.

مسائل بهینه سازی مقید مربوط به کاربردهایی هستند که در آن‌ها قیدهای صریحی (Explicit Constraints) رو متغیرهای مسأله تعریف شده است. قیدهای تعریف شده روی این دسته از مثال می‌توانند کران‌های (Bounds) ساده و یا سیستم‌هایی از معادلات و نامعادلات باشند که روابط میان متغیرهای مسأله را مدل می‌کنند.

همچنین مسائل بهینه‌سازی مقید را می‌توان بر اساس طبیعت قیدهای تعریف شده رو متغیرها (به عنوان نمونه، خطی، غیر خطی، محدب و سایر موارد) و هموار بودن توابع (به عنوان نمونه، مشتق‌پذیر (Differentiable) یا نامشتق‌پذیر (Non-Differentiable))، به طبقه‌های دیگری دسته‌بندی کرد.

مسائل بهینه سازی «قطعی» (Deterministic) و بهینه سازی «تصادفی» (Stochastic)

در مسائل بهینه سازی قطعی، فرض بر این است که داده‌های مسأله داده شده به طور دقیق شناخته شده هستند. با این حال و به دلایل مختلفی، داده‌های بسیاری از مسائل داده شده را به طور دقیق نمی‌توان شناخت (یا در اختیار داشت). اولین دلیل برای در دسترس نبودن داده‌های دقیق مسأله، «خطای اندازه‌گیری» (Measurement Error) داده‌ها است. دلیل دوم و بسیار مهم برای شناخته نبودن داده‌های مسأله این واقعیت است که برخی از داده‌ها، اطلاعات مرتبط با آینده را نمایش می‌دهند (نظیر تقاضا برای یک محصول یا قیمت یک محصول در آینده) که نمی‌توان با قطعیت (Certainty) آنها را شناخت.

در بهینه سازی همراه با عدم قطعیت (Optimization Under Uncertainty) یا بهینه سازی تصادفی (Stochastic Optimization)، عدم قطعیت در مدل ترکیب شده است. تکنیک‌های «بهینه سازی استوار» (Robust Optimization) تنها زمانی می‌توانند مورد استفاده قرار بگیرند که پارامترهای مسأله درون کران‌های مشخصی قرار گرفته باشند؛ در چنین حالتی، هدف پیدا کردن پیدا کردن جوابی است که به ازاء تمامی داده‌ها، امکان‌پذیر (یا قابل قبول) و به نحوی بهینه باشد.

مدل‌های بهینه سازی تصادفی (Stochastic Optimization)، از این واقعیت که «توزیع احتمالی» (Probability Distribution) حاکم بر داده‌ها مشخص و یا قابل تخمین است، بهره می‌برند؛ در چنین حالتی، هدف پیدا کردن یک سیاست (Policy) است که برای تمامی (یا تقریبا تمامی) نمونه‌های داده قابل قبول باشد و عملکرد مورد انتظار مدل (یا سیستم) را بهینه سازی کند.

مسائل بهینه سازی بدون هدف، تک هدفه و چند هدفه

بیشتر مسائل بهینه‌سازی، از یک تابع هدف برخوردار هستند. با این حال، مسائل بهینه سازی جالبی می‌توان پیدا کرد که یا هیچ تابع هدفی ندارند و یا از چندین تابع هدف برخوردار هستند. «مسائل امکان‌پذیری» (Feasibility Problems) مسائلی هستند که در آن‌ها، هدف پیدا کردن مقادیری برای متغیرها است که قید‌های مدل را ارضا کنند؛ در چنین حالتی مدل، تابع هدف خاصی ندارد که بخواهد آن را بهینه سازی کند. «مسائل مکملی» (Complementarity Problems)، مسائل بسیار فراگیری در مهندسی و اقتصاد محسوب می‌شوند؛ در چنین مواردی، هدف مدل‌های بهینه سازی پیدا کردن جوابی است که «شرایط مکملی» (Complementarity Conditions) مسأله را ارضا کند.

«مسائل بهینه سازی چند هدفه» (Multi-Objective Optimization Problems) در بسیاری از حوزه‌های علمی و کاربردی نظیر مهندسی، اقتصاد و «لجستیک» (Logistics) کاربرد دارند و زمانی مورد استفاده قرار می‌گیرند که برای رسیدن به تصمیمات بهینه در سیستم، نیاز است میان دو یا چند «هدف متناقض» (Conflicting Objectives) موازنه برقرار شود. به عنوان نمونه، توسعه یک مؤلفه جدید ممکن است نیازمند کمینه کردن وزن و به طور همزمان، بیشینه کردن قدرت باشد. همچنین، جهت انتخاب سبد سرمایه‌گذاری مناسب باید به نحوی عمل کرد که بازگشت مورد انتظار سرمایه، بیشینه و ریسک سرمایه گذاری، کمینه گردد.

در عمل، برای بهینه سازی مسائل چند هدفه، از راهکارهایی استفاده می‌شود که در آن‌ها، مسائل چند هدفه (Multi-Objective) به مسائل تک هدفه (Single-Objective) تبدیل می‌شوند؛ در این دسته از راهکارها، از طریق تشکیل یک ترکیب وزن‌دار از توابع هدف مختلف و یا به وسیله جایگزین کردن توابع هدف با قیدهای مشخص، مسائل بهینه سازی چند هدفه به مسائل تک هدفه تبدیل می‌شوند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

  • مجموعه آموزش‌های الگوریتم‌‌های بهینه‌‌سازی هوشمند
  • آموزش تئوری و عملی الگوریتم‌های ژنتیک
  • مجموعه آموزش‌‌های هوش مصنوعی
  • مجموعه آموزش‌‌های الگوریتم‌های ژنتیک و محاسبات تکاملی
  • الگوریتم بهینه‌سازی فاخته — از صفر تا صد
  • الگوریتم ژنتیک — از صفر تا صد
  • الگوریتم کلونی مورچگان — از صفر تا صد
  • الگوریتم کرم شب تاب — از صفر تا صد

^^

telegram
twitter
neos GuideWikipedia

مرتضی جادریان

«مرتضی جادریان»، دانشجوی مقطع دکتری مهندسی کامپیوتر گرایش هوش مصنوعی است. او در زمینه سیستم‌های هوشمند، به ویژه سیستم‌های هوشمند اطلاعاتی، روش‌های یادگیری ماشین، سیستم‌های دانش محور و محاسبات تکاملی فعالیت دارد.

نوشته بهینه سازی (ریاضیاتی) چیست؟ — راهنمای جامع اولین بار در مجله فرادرس. پدیدار شد.