📂Optimization

What is a Genetic Algorithm?

정의 ¹

$$ \argmax_{\mathbf{x} \in X} f \left( \mathbf{x} \right) $$ In an optimization problem that maximizes the objective function $f : X \to \mathbb{R}$, the following three operations repeated iteratively are called a 유전 알고리즘.

• 자연선택: Select superior solutions from the current set of solutions to form the next generation’s solution set.
• 교차혼합: Select multiple solutions from the solution set and exchange parts of their information to generate new solutions.
• 돌연변이: Randomly alter parts of some solutions in the solution set to secure diversity.

설명

유전 알고리즘은 다윈의 진화론에서 적자생존에 영감을 받은 개체군 메서드로써, 각각의 개체는 염색체라 불리는 벡터 $\mathbf{x} \in X$ 로 표현되며 $f \left( \mathbf{x} \right)$ 와 같이 평가되어 그 함수값 자체를 적합도로 삼는다. 진화론의 비유에서 $f$ 는 환경 그 자체를 의미하며, 우리가 원하는 것은 이 환경에서 가장 잘 살아남는, 즉 $f$ 가 최대가 되는 $\mathbf{x}$ 를 찾는 것이다.

자연선택

As in the exposition of natural selection in evolutionary theory, evolution is not the purposeful development of organs or physiologies but rather the repeated phenomenon in which individuals with lower fitness are eliminated and those with higher fitness survive.

In a genetic algorithm, natural selection is implemented simply as an operation that removes low-fitness solutions from the solution set, and it is fundamentally the driving force that causes the genetic algorithm to operate.

교차혼합

From an optimization perspective, crossover is a global search method intended to explore the solution space broadly; by producing abrupt changes rather than incremental ones, it helps prevent convergence to local optima. This is consistent with the biological analogy, where sexual reproduction—often explained as a strategy to resist parasites—favors explosive diversity generation.

돌연변이

Mutation is implemented as small changes to the chromosome and, in contrast to crossover, has the character of a local search method. If one were to repeat only natural selection without mutation, the final solution would effectively be determined in the first generation without needing further generations; mutation is the mechanism that, at the risk of failure, induces small variations to discover better solutions.