지능형시스템/최적화4 [최적화] 입자 군집 최적화 (Particle Swarm Optimization, PSO)의 개념과 구현 1. 군집 기반 최적화 (Swarm-Based Optimization) 군집 기반 최적화는 수리적 최적화의 한 방법론으로써, 군집 기반 최적화에서는 여러 개의 optimizer가 서로 정보를 교환하며 동시에 최적화를 수행한다. 그림 1은 경사하강법 (gradient descent method)와 같은 single agent optimization과 PSO와 같은 swarm-based optimization의 차이를 개념적으로 보여준다. Single agent optimization에서는 주어진 법칙에 따라 최적해를 찾아간다. 대표적으로 경사하강법에서는 함수의 gradient를 따라 최적해를 찾아간다. 반면에 PSO와 같은 swarm-based optimization에서는 주어진 법칙에 더하여 agent .. 2021. 7. 25. [최적화/전역 최적화] Tabu Search Tabu search는 simulated annealing, genetic algorithm 등과 같이 최적화 문제의 형태에 상관없이 주어진 최적화 문제를 풀기 위한 메타휴리스틱 (metaheuristic) 알고리즘이다. 기존의 simulated annealing, genetic algorithm과 같은 최적화 알고리즘들은 기본적으로 neighbor search를 기반으로 동작하기 때문에 current solution이 개선되는 방향으로만 진행하려는 성질이 있다. 이러한 성질로 인해 simulated annealing 및 genetic algorithm은 빈번하게 [그림 1]과 같은 지역 최적점 (local optimum)에 수렴한다. Tabu search는 빈번하게 지역 최적점에 수렴하는 문제를 해결하.. 2016. 9. 28. [수리적 최적화] 유전 알고리즘 (Genetic Algorithm)과 전역 최적화 1. 유전 알고리즘 (Genetic Algorithm) 소개 유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 최적화 방법이다. 유전 알고리즘은 이론적으로 전역 최적점을 찾을 수 있으며, 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있기 때문에 다양한 응용에서 매우 활발히 이용되고 있다. 일반적으로 유전 알고리즘에 대해 알고리즘이라는 표현을 이용하지만, 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 최적화 문제를 풀기 위한 일반적인 방법론에 가깝다. 즉, 모든 문제에 적용 가능한 하나의 알고리즘이나 소스 코드가 있는 것이 아니기 때문에 유전 알고리즘의 원리를 이해하고, 이를 자신이 원하는 문제에 적용할 수 있도록 설계하는 것이 중요하다. 유전.. 2016. 9. 16. 라그랑주 승수법 (Lagrange Multiplier Method) 라그랑주 승수법 (Lagrange multiplier method)은 프랑스의 수학자 조세프루이 라그랑주 (Joseph-Louis Lagrange)가 제약 조건이 있는 최적화 문제를 풀기 위해 고안한 방법이다. 라그랑주 승수법은 어떠한 문제의 최적점을 찾는 것이 아니라, 최적점이 되기 위한 조건을 찾는 방법이다. 즉, 최적해의 필요조건을 찾는 방법이다. 1. 기하학적 해석 라그랑주 승수법의 기본 가정은 "제약 조건 $g$를 만족하는 $f$의 최솟값 또는 최댓값은 $f$와 $g$가 접하는 지점에 존재할 수도 있다."는 것이다. 아래의 [그림 1]은 제약 조건 $g(x, y) = c$를 만족하는 $f(x, y)$의 최댓값을 구하는 문제를 나타낸다. 만약, $f(x, y)$의 최댓값을 $k$라고 하면, $k$.. 2016. 9. 1. 이전 1 다음
