플라이 알고리즘

다음 시리즈의 일부
진화 알고리즘
인공발달성 인공생명체 세포진화 알고리즘 문화 알고리즘 미분진화 효과적인 피트니스 진화 연산 진화전략 가우스 적응 진화적 다중모드 최적화 입자 군집 최적화 메미틱 알고리즘 자연 진화 전략 신경진화 프로모터 기반 유전 알고리즘 나선 최적화 알고리즘 자체수정코드 다형 코드
유전 알고리즘
염색체 클론 선택 알고리즘 크로스오버 돌연변이 유전적 기억력 유전 퍼지 시스템 선택 플라이 알고리즘
유전자 프로그래밍
데카르트 유전 프로그래밍 선형유전자프로그래밍 문법적 진화 다중 표현식 프로그래밍 유전적 개선 스키마 유리스코 패리티 벤치마크
v t

이 기사의 주요 기고자는 그 주제와 밀접한 관련이 있는 것으로 보인다.위키피디아의 콘텐츠 정책, 특히 중립적인 관점을 준수하기 위해 정리가 필요할 수 있다.자세한 내용은 대화 페이지에서 논의하십시오. (2018년 7월)(이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

역사

플라이 알고리즘은 파리식 접근법에 기초한 협력적 공진화의 일종이다.^[1]플라이 알고리즘은 컴퓨터 스테레오 비전에 Evolution 알고리즘을 적용하는 범위에서 1999년에 처음 개발되었다.^[2][3]3-D 정보를 얻기 위해 영상 원형을 추출한 뒤 일치시키는 스테레오비전(steervision)에 대한 고전적인 영상 기반 접근 방식과 달리 플라이 아고리즘은 장면의 3-D 공간을 직접 탐색하는 것에 기반을 두고 있다.파리는 좌표(x, y, z)에 의해 설명되는 3-D 포인트로 정의된다.일단 카메라의 시야에 해당하는 검색 공간에서 무작위적인 파리 개체 수가 생성되면, 그 진화(진화 전략 패러다임 기반)는 이미지 투영의 일관성을 바탕으로 물체의 가시 표면에 파리가 얼마나 누워있을 가능성을 평가하는 피트니스 기능을 사용했다.이를 위해 피트니스 기능은 계산된 플라이 돌출부의 회색 수준, 색상 및/또는 질감을 사용한다.

Fly Algorithm의 첫 번째 응용 분야는 스테레오비전이었다.^[2][3][4][5]기존의 '이미지 우선순위' 접근법은 3-D 모델을 구축하기 위해 스테레오 영상에서 일치하는 기능을 사용하는 반면, 플라이 알고리즘은 3-D 공간을 직접 탐색하고 영상 데이터를 사용하여 3-D 가설의 타당성을 평가한다."다이내믹 플라이"라고 불리는 변종은 파리를 파리의 속도를 포함하는 6-업플(x, y, z, x, y', y', z')로 정의한다.^[6][7]속도 구성요소는 피트니스 계산에서 명시적으로 고려되지 않지만 업데이트되는 파리의 위치에서 사용되며 유사한 유전적 연산자(교차, 교차)의 대상이 된다.

차량^[8] 내 장애물 회피에 파리 적용은 파리 개체수가 시간을 준수하고 지속적으로 장면의 표현을 진화시켜 파리로부터 차량 제어 신호를 직접 발생시킨다는 점을 악용한다.최적화하는 피트니스 기능에 대한 추가 용어로 다른 센서(예: 음향 근접 센서 등)를 추가할 수 있기 때문에 플라이 알고리즘의 사용은 스테레오 영상에 엄격하게 제한되지 않는다.또한 비행측정 정보는 파리 위치의 업데이트 속도를 높이는 데 사용될 수 있으며, 반대로 파리 위치는 국지화 및 지도화 정보를 제공하는 데 사용될 수 있다.^[9]

플라이 알고리즘의 또 다른 적용 분야는 핵의학에서 방출 단층촬영을 위한 재구성이다.플라이알고리즘은 단일광자 방출 컴퓨터 단층^[10] 촬영과 양전자 방출 단층^[11] 촬영에 성공적으로 적용되었다.^[12]여기서 각 파리는 광자 방출기로 간주되며, 그 적합성은 센서에서 관찰된 실제 패턴과 센서의 시뮬레이션된 조명의 적합성에 기초한다.이 애플리케이션 내에서 피트니스 기능이 새로운 개념의 '마진 평가'를 사용하도록 다시 정의되었다.여기서, 한 개인의 건강은 세계 인구의 질에 대한 그것의 (긍정적이거나 부정적인) 기여로 계산된다.그것은 1회차 교차 검증 원칙에 기초한다.글로벌 피트니스 함수는 전체 모집단의 품질을 평가한다. 오직 개인의 피트니스(파리)는 개별 피트니스 함수를 평가해야 하는 특정 플라이를 가진 모집단과 그렇지 않은 모집단의 글로벌 피트니스 가치의 차이로 계산된다.^[13][14]각 파리의 체력에서는 '신뢰도 수준'으로 간주된다.복셀화 과정에서 암묵적 모델링(예: 메타볼)을 사용하여 파리의 개별 발자국을 수정하는 데 사용된다.보다 정확한 매끄러운 결과를 만들어 낸다.

더 최근에는 모자이크 같은 이미지나 스프레이 페인트를 생성하기 위해 디지털 아트에 사용되었다.^[16]영상의 예는 YouTube에서 찾을 수 있다.

파리의 진화

여기서 개인의 인구는 개인이 공동의 목표를 향해 협력하는 사회로 간주된다.이것은 모든 공통 유전 연산자를 포함하는 진화 알고리즘을 사용하여 구현된다(예: 돌연변이, 크로스오버, 선택).주요 차이점은 피트니스 기능이다.여기에서 두 가지 수준의 피트니스 기능이 사용된다.

• 특정 개인의 성과를 평가하기 위한 로컬 피트니스 기능(일반적으로 선택 과정 중에 사용됨.
• 전체 모집단의 성능을 평가하는 글로벌 피트니스 기능.이러한 글로벌 피트니스를 극대화(또는 고려된 문제에 따라 최소화)하는 것이 인구의 목표다.

또한 검색 공간의 일부 영역에만 개인이 모이는 것을 피하려면 다양성 메커니즘이 필요하다.또 다른 차이점은 진화 루프가 종료되면 문제 해결책의 추출이다.고전적 진화론적 접근법에서 가장 우수한 개인은 해법에 대응하고 나머지 개체군은 폐기한다.여기서 모든 개인(또는 모집단의 하위 그룹의 개인)을 취합하여 문제 해결 방법을 구축한다.피트니스 기능 구성 방식과 솔루션 추출 방법은 물론 문제에 의존한다.

파리 Evolution 애플리케이션의 예는 다음과 같다.

• 플라이 알고리즘.
• 텍스트 마이닝.
• 손짓 인식.
• 산업용 농식품 프로세스에서 복잡한 상호작용을 모델링.
• 양전자 방출 단층 촬영 재구성.

불화

파리식 접근법 vs 협력적 공진화

협력적 공진화는 복잡한 문제를 독립적으로 해결하는 하위 구성 요소로 분해하여 해결하는 광범위한 진화 알고리즘이다.파리의 접근법은 협동 진화 알고리즘과 많은 유사점을 공유한다.파리의 접근방식은 단일 모집단을 사용하는 반면, 다종류는 협력적 공진화 알고리즘에서 사용될 수 있다.고전적 진화 알고리즘, 협동적 공진화 알고리즘, 파리 진화에서 유사한 내부 진화 엔진이 고려된다.협력적 공진화 알고리즘과 파리의 진화 사이의 차이는 인구의 의미론에 있다.협력적 공진화 알고리즘은 큰 문제를 하위문제(개인의 그룹)로 나누고 큰 문제를 향해 분리해 해결한다.^[17]서로 다른 하위 집단의 개인들 사이에는 동일한 하위 집단의 개인들과만 상호 작용/교배가 없다.그러나 파리의 진화 알고리즘은 하나의 큰 요소로서 모든 문제를 해결한다.모든 인구의 개인은 전체 인구를 검색 공간의 매력적인 지역으로 몰기 위해 협력한다.

플라이 알고리즘 대 입자 군집 최적화

협력적 공진화와 입자 군집 최적화(PSO)는 많은 유사점을 공유한다.PSO는 새가 몰려오거나 물고기 떼를 쓰는 사회적 행동에 의해 영감을 받는다.^[18][19]처음에는 컴퓨터 그래픽에 실감나는 애니메이션을 위한 도구로 도입되었다.개인의 행동 규칙(임의 생성기를 사용할 수도 있음)을 조정하여 시각적으로 현실적인 집단 행동을 구축하기 위해 서로 상호작용하는 복잡한 개인을 이용한다.수학적 최적화에서, 무리의 모든 입자들은 어떻게든 무리의 가장 좋은 입자 쪽으로 치우친 자신의 무작위 경로를 따른다.플라이 알고리즘에서 파리는 실제 센서 데이터에서 장면의 공간 표현을 만드는 것을 목표로 한다. 파리는 의사소통하거나 명시적으로 협조하지 않으며 행동 모델을 사용하지 않는다.

두 알고리즘 모두 일련의 랜덤 솔루션으로 시작하는 검색 방법이며, 이는 글로벌 최적화를 위해 반복적으로 수정된다.단, Fly 알고리즘의 최적화 문제의 해결책은 모집단(또는 모집단의 하위 집합)이다.파리는 암암리에 협력하여 해결책을 만든다.PSO에서 해결책은 단일 입자로, 가장 적합한 입자다.플라이 알고리즘과 PSO와의 또 다른 주요한 차이점은 플라이 알고리즘이 어떤 행동 모델에 기초하지 않고 기하학적 표현만을 구축한다는 것이다.

플라이 알고리즘nm의 응용

• 컴퓨터 스테레오 비전^[2][3][4][5]
• 장애물 회피^[6][8][7]
• 동시 로컬리제이션 및 매핑(SLAM)^[9]
• 싱글 포톤 방출 컴퓨터 단층 촬영(SPECT) 재구성
• 양전자 방출 단층 촬영(PET) 재구성
• 디지털 아트^[16][21]

예:단층 촬영 재구성

단층 촬영 재구성은 데이터 누락 및/또는 노이즈로 인해 종종 잘못 노출되는 역문제다.역문제의 답은 독특하지 않으며, 극한 소음 수준의 경우에는 존재하지도 않을 수 있다.재구성 알고리즘의 입력 데이터는 ${\displaystyle \mathrm{재구성}}$할 데이터의${\displaystyle }$라돈$$ 변환 또는 시노그램$({\displaystyle Y}$) ${\$\left$(Y\right)}$으로 제공될 수 있다(f )${\$right$)\}.$ $f{\displaystyle }$ ${\$$displaystystyle f$$}$을 알 수 없음$$; Y${\}.$단층 촬영의 데이터 수집은 다음과 같이 모델링할 수 있다.

$[\displaystyle Y=P[f]+\epsilon }$

여기서 $P{\displaystyle }$ ${\displaystyle P}$은(는) 시스템 매트릭스 또는 투영 연산자이고 $and{\displaystyle }$ ${\displaystyle \epsilon }$은(는) 일부 포아송 노이즈에 해당한다.이 경우 재구성은 라돈 변환의 역방향에 해당한다.

${\displaystyle f=P^{-1}[Y]}$

$P{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$는 노이즈, 획득 기하학 등을 설명할$$ 수 있다는 점에 유의하십시오.플라이 알고리즘은 반복재건의 한 예다.단층 재구성의 반복 방법은 비교적 모델링하기 쉽다.

${\displaystyle {\f}=\operatorname {arg\,min}Y-{{} _{2}^{2}}$

어디 f^{\displaystyle{\hat{f}}}f{\displaystyle f}의(여기 ℓ2-norm지만, 다른 오류 측정 사용될 수 있)Y{Y\displaystyle}, Y^{\displaystyle{\hat{Y}}의 오류 측정을 최소화의 예측}은. regularisation 용어고 overfitting를 막기 위해 도입할 수 있습니다. s가장자리를 보존하는 동안 나무늘보 소음.반복적인 방법은 다음과 같이 실행할 수 있다.

(i) 재구성은 영상의 초기 추정치(일반적으로 상수 영상), (ii) 투영 데이터는 이 영상에서 계산되며, (iii) 추정된 투영을 측정된 투영과 비교하고, (iv) 보정(v) 추정 영상을 수정하기 위해 수행되며, (v) 알고리즘은 e가 수렴될 때까지 반복된다.자극 및 측정된 투영 세트. 

아래의 유사코드는 단층 재구성을 위한 Fly Algorithm에 대한 단계별 설명이다.알고리즘은 정상 상태 패러다임을 따른다.예증을 위해, 유사분열,^[22][23] 이중 돌연변이 등과 같은 진보된 유전자 조작자는 무시된다.JavaScript 구현은 Fly4PET에서 확인할 수 있다.

알고리즘 fly-algorithm은 입력:파리의 수(N), 입력 프로젝션 데이터(선호)출력:파리는 인구(F), 돌출부 F에서 3D볼륨 F(veryfair날씨 맑음)postcondition의 voxelisation에 해당하는(pestimated)추정:선호도pestimatedm. 책임 사이의 차이inimal.START 1. // 초기화 2. // N 파리의 위치를 설정한다. 즉, 플라이 모집단의 각 파리에 대해 초기 추측 3. F do 4. F(i)x ← 무작위(0, 1) 5. F(i)y random 무작위(0, 1) 6. F(zi) ← (0, 1) 7.8estimated. 9. // 모집단의 성과를 계산한다(즉, 글로벌 피트니스). 10fitness. G(F) ← 오류metrics(preference, pestimated) 11. 12. f fkill F. 14의 무작위 플라이를 선택한다.f의kill 기여를estimated 15. 16. // f 17kill 없이 모집단의 성과를 계산한다. Gfitness(F-{fkill}) ← 오류metrics(preference, pestimated) 18. 19. // 성과 비교, 즉 플라이의 로컬 피트니스 20. Lfitness(fkill) ← Gfitness(F-{Fkill}) - Gfitness(F) 21. 22.만약 그 지역 휘트니스 0보다 크면//Thresholded-selection 나쁜 파리의. 그 단계 26일까지 가. 끓여fkill은 좋은 파리(때 fkill 포함된 인구의 성능 더 좋다):24를 죽이지 않아야 한다. 다른 단계 28에 갑니다. 끓여fkill은 나쁜 파리 때 fkillincl 있는 경우 국민들의 성능 더 나쁘다 23살해될 수 있다.uded):우리가 할 수 있 25.26을 없애라.파리의 기여를 복원한 후 12. 27. 28 단계로 이동하십시오.유전자 조작자 29. 30을 선택한다.유전자 조작자가 돌연변이인 경우 31. 그 다음 34. 32 단계로 간다. 그렇지 않으면 50. 33. 34reproduce. f ← 무작위 플라이를 F 35. 14로 선택한다.. 계산하다 국민들의 성능 freproduce 39없이//pestimated 37.38에서 freproduce의 기여를 제거한다.Gfitness(화씨{freproduce})← Errormetrics(선호도 pestimated)40.41. //, 즉 파리 지역 휘트니스 42compute에서 공연을 비교하여라.Lfitness(freproduce)← Gfitness(화씨{freproduce})-Gfitness(F)4344.파리의 기여도를 45.46으로 회복한다.지역적 체력이 0보다 낮거나 같으면 // 47을 번식할 수 있는 좋은 파리의 한계선 선택. 그렇지 않으면 34단계로 가. // f는kill 나쁜 파리: 48을 번식하도록 허용해서는 안 된다. // f는kill 좋은 파리: 49. 50. // 새로운 혈액 / 이민 51.f를kill 임의의 위치로 새 플라이로 교체하고 57. 52. 53. // 돌연변이 54로 이동하십시오.f를reproduce f 55에kill 복사한다.약간kill 그리고 임의로 f의 위치를 56. 57.새 파리가 모집단에 기여한 공로를 58.59에 더한다.재구성을 중지할 경우 60. 그 다음 63. 61. 10. 또는 62. 63. // 솔루션 64를 추출하십시오.VF ← F 65.66 복셀화. VF END 복귀

예:디지털 예술.

이 예에서 입력 이미지는 타일 집합(예: 고대 모자이크에서와 같이)에 의해 근사치되어야 한다.타일은 방향(각도 angle), 세 가지 색 구성 요소(R, G, B), 크기(w, h) 및 위치(x, y, z)가 있다.N 타일이 있으면 9N개의 알 수 없는 부동소수 번호가 있다.다시 말해 5000개의 타일에는 45,000개의 숫자가 있다.최적화 문제의 답이 최고의 개인인 고전적 진화 알고리즘을 사용하면 개인의 게놈은 45,000개의 유전자로 구성될 것이다.이 접근방식은 복잡성과 계산 시간의 측면에서 비용이 매우 많이 들 것이다.고전적 최적화 알고리즘도 마찬가지다.플라이 알고리즘을 사용하면 모든 개인은 타일을 모방하며, 인구의 성과에 대한 기여도(글로벌 피트니스)를 평가하기 위해 지역적 피트니스(local fitness)를 사용하여 개별적으로 평가할 수 있다.여기 개인은 9N 대신에 9개의 유전자를 가지고 있고, N개의 개인은 있다.다음과 같이 재건 문제로 해결할 수 있다.

${\displaystyle reconstruction=\operatorname {arg\,min} {x<W}{\underset {y=0}{\sum }}{j<H}{j=0}{\sum }}입력(x,y)-P[x,y) }}}}}}}} {\overset {x}$

여기서 ${\displaystyle \mathrm{in}}$ ${\displaystyle p}$ ${\displaystyle u}$ t ${\displaystyle input}$은(는) 입력 이미지, $x{\displaystyle }$ ${\displaystyle x}$$$및 $y{\displaystyle }$ {\$displaystyle y}$은(는) 수평 및 $수직{\displaystyle }$ 축을 따라가는 픽셀 좌표, $W{\displaystyle }$ ${\displaystyle H}$은(각) 이미지 너비와 높이, F ${\sty$)이다.$Le$ F$}$은 파리 개체군이며$$, $P{\displaystyle }$ ${\displaystyle P}$은(는) 파리로부터 이미지를 생성하는 투영 연산자다.이 투영 연산자 $P{\displaystyle }$ ${\displaystyle P}$는 여러 형태를 취할 수 있다$$.그녀의 작품에서, Z.알리 아부드(Ali Abudd)는 OpenGL을 사용하여 다른 효과(예: 모자이크 또는 스프레이 페인트)를 생성한다.피트니스 기능의 평가 속도를 높이기 위해 OpenCL도 사용한다.알고리즘은 무작위로 생성된$$ $모집단{\displaystyle }$F {\$displaystyle$ F$}$로 시작한다(위 알고리즘의 라인 3 참조).− P(), y){\displaystyle G_{피트니스}(F)={\overset{x<[F]F{F\displaystyle} 다음 Gf계산하려면 글로벌 피트니스를 사용하여 나는 하루에 500파운드 ness(F))∑ y=0<>W∑ j=0j<>Hi의 스녀 p너지(), y);으로 평가된다.W}{\underset{y=0}{\sum}}}{\overset{j<.H}{\underset{j=0}{\sum}}}inputᆩ-P[F](x, y)}(s10호선).${\displaystyle G_{}}$ ${\displaystyle f_{}}$ ${\displaystyle i_{}}$ ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\displaystyle e_{}}$ ${\displaystyle s_{}}$ ${\$은(는) 오류 메트릭이므로 최소화해야 한다.

참고 항목

• 수학적 최적화
• 메타휴리스틱
• 검색 알고리즘
• 확률적 최적화
• 진화 연산
• 진화 알고리즘
• 유전 알고리즘
• 돌연변이(유전자 알고리즘)
• 교차(유전자 알고리즘)
• 선택(유전자 알고리즘)

참조