최적화

II. 최적화

“AI에 관해 이야기할 때 무엇을 의미하나요?”라고 질문할 수도 있습니다. 심층 신경망 및 복잡한 알고리즘과 같이 매우 발전된 것입니까, 아니면 소프트웨어에 대한 멋진 단어입니까?

안타깝게도 정확한 정의를 내릴 수는 없습니다. 왜? 왜냐면 하나도 없거든요. AI 분야에는 일반적으로 합의된 정의가 없습니다(AI 소개 과정의 1장에서 이 주제에 대해 자세히 논의합니다). 우리는 AI라고 부르는 것이 적절한지 여부를 결정하는 것은 기술 자체보다는 기술이 사용되는 방식에 따라 결정되는 경우가 많다고 주장합니다.

참고!

적절한 사례: 최적화

사용 사례에 따라 AI일 수도 있고 아닐 수도 있는 좋은 예는 최적화입니다. 보시다시피 일부 최적화 알고리즘은 매우 간단하며 몇 줄의 코드로 구현할 수 있습니다. 그러나 우리는 그 결과가 지능적인 행동으로 간주될 수 있다고 주장할 것이며, 우리 중 많은 사람들이 이를 주저 없이 AI라고 부를 것입니다.

AI 소개(2장)에서 우리는 하노이 타워나 치킨 크로싱 퍼즐과 같은 다양한 "두뇌 놀이" 또는 퍼즐이 검색 문제로 공식화되고 시작점에서 목표까지의 경로를 찾아 간단한 방식으로 해결될 수 있는 방법을 보여주었습니다.

프로그래밍의 초능력이 있으면 연필과 종이로 모든 것을 해결해야 했던 이전보다 훨씬 더 큰 문제로 확장할 수 있습니다. 우리는 소위 순회 판매원 문제(또는 TLA를 좋아하는 사람들을 위한 TSP)라는 완전히 고전적인 문제부터 시작할 것입니다.

참고!

예시 최적화 작업

파인애플을 실은 컨테이너 선박의 항로를 계획하는 임무를 받았다고 상상해 보세요. 배는 맛있는 공정무역 파인애플을 실은 파나마에서 출발합니다. 파인애플을 갈망하는 시민들이 간절히 기다리고 있는 뉴욕, 카사블랑카, 암스테르담, 헬싱키 등 4개의 항구가 있습니다. 선박은 4개의 목적지 항구를 정확히 한 번만 방문해야 하지만 각 항구를 방문하는 순서는 자유입니다. 목표는 탄소 배출을 최소화하는 것입니다. 즉, 긴 경로보다 짧은 경로가 더 좋습니다.

가능한 모든 대안을 나열하는 것부터 시작하여 각 단계를 개별적으로 고려해 보겠습니다. 프로그래머가 사용하는 용어는 열거형입니다. 따라서 먼저 가능한 모든 경로를 열거하겠습니다. 조합론(유한한 물체 집합의 조합을 다루는 수학의 일부)에 정통한 분들은 경로의 수가 다음과 같다는 것을 아실 것입니다. 4×3×2×1=24 4×3×2×1=24.

헬싱키의 모든 사람들이 파인애플 알레르기가 있다면 몇 개의 경로가 있을까요? 즉, 특정 출발지에서 다른 3개의 항구(4개가 아닌)까지의 경로 수는 얼마입니까?

단순히 대안을 나열하는 것은 별로 유용하지 않지만 적어도 경로의 수가 너무 많아지기 시작하여 수동으로 가장 좋은 경로를 찾는 것이 자질구레한 일이라는 것을 깨닫는 데 도움이 됩니다. 있다 24 5개 항구에 대한 24개 노선(그 중 하나가 출발점). 런던과 같은 곳에서도 파인애플을 원할 경우 경로의 5개 위치에 추가할 수 있으므로 경로 수는 다음과 같습니다. 5×24=120 5×24=120. 또 다른 목적지를 사용하면 이 숫자에 6을 곱하여 다음을 얻을 수 있습니다. 6×120=720 6×120=720개의 다른 경로 등.

참고!

공식1×2×3×... 1×2×3×... 은 계승이라고 불리며 정말 빠르게 커집니다. 에 대한 10 목적지는 10개(파나마 출발지 외에), 노선 수는 이미 3,628,800 3,628,800. 이는 매우 빠르게 수동 솔루션이 완전히 불가능하다는 것을 의미합니다.

컴퓨터를 사용한 자동 솔루션은 우리를 훨씬 더 발전시킬 수 있습니다. 그러나 작업 부하를 줄이기 위한 현명한 전략이 없으면 컴퓨터라도 조만간 질식하게 될 것입니다. 여기에 더 발전된 AI 기술이 개입합니다. 하지만 너무 서두르지 말고 탄소 배출을 최소화하면서 파인애플을 4개 도시에 배달할 수 있는 경로를 찾아보세요.

대안을 나열한 후 다음으로 각 대안의 탄소 배출량을 계산할 수 있습니다. 아래에서는 5x5 테이블에서 포트 간 거리를 킬로미터 단위로 확인할 수 있습니다.

PAN AMS 카스 뉴욕 헬
팬 0 8943 8019 3652 10545
AMS 8943 0 2619 6317 2078
CAS 8019 2619 0 5836 4939
뉴욕 3652 6317 5836 0 7825
헬 10545 2078 4939 7825 0

보트가 비교적 현대적이며 우리가 배송하는 파인애플 양에 대해 킬로미터당 0.020kg의 CO2 배출량을 생성한다고 가정해 보겠습니다. 따라서 먼저 표의 첫 번째 행, 두 번째 열에서 거리(위 표에서 강조 표시됨)인 8943km를 찾은 다음 이를 0.020kg/km로 곱하면 178.9kg이 됩니다.

참고표를 이용하여 다음 세 가지 경로에서 발생하는 배출량을 계산해 보세요. 어느 것이 가장 적은 배출량을 생성합니까?

PAN AMS 카스 뉴욕 헬
팬 0 8943 8019 3652 10545
AMS 8943 0 2619 6317 2078
CAS 8019 2619 0 5836 4939
뉴욕 3652 6317 5836 0 7825
헬 10545 2078 4939 7825 0

위의 모든 연습에는 어느 것이 더 나은 선택인지 항상 결정할 수 있도록 다양한 대안의 순위를 매기는 기준 또는 점수가 있었습니다. 예를 들어 파인애플 배송 문제에서는 경로의 전체 길이나 탄소 배출량이 기준이었고 우리는 항상 배출량이 가장 적은 짧은 경로를 선호했습니다.

위의 연습은 그러한 기준을 고안할 수만 있다면 문제 해결 작업이 간단한 최적화 작업이 된다는 것을 보여주기 위한 것입니다. 대안의 수가 정말, 정말 클 수 있기 때문에 이것이 반드시 쉬운 작업이 될 것이라는 말은 아닙니다. 단순히 모든 단일 옵션을 반복하고 최선의 것을 선택하는 우리가 사용한 접근 방식을 무차별 접근 방식이라고 합니다.

참고!

무력만으로는 충분하지 않을 때

컴퓨터가 빠르다는 말은 절제된 표현입니다. 최신 프로세서는 기가헤르츠(GHz) 단위로 측정되는 속도, 즉 초당 수십억 개의 명령을 처리합니다. 따라서 우리는 가능한 모든 솔루션을 단순히 반복하는 무차별 접근 방식을 사용하여 많은 일을 할 수 있습니다. 그러나 우리가 해결하고 있는 문제 중 상당수는 조합 폭발이라는 현상으로 인해 가장 빠른 컴퓨터조차 질식할 정도입니다. 이러한 문제에 대해 무차별 접근 방식은 문제 크기(예: 포트 수)가 매우 작지 않는 한 너무 느립니다. 이는 최적의 솔루션 대신 좋은 솔루션에 만족해야 함을 의미할 수 있습니다.