수학적으로 분할 문제를 표현하기 위해 몇가지 정의를 따를 필요가 있다.
1. 그래프 G는 가중치 w를 가지는 n개의 노드로 구성
2. p는 양수
3. 행렬 C는 그래프 G에 대한 연결 가중치 행렬이다.
4. k는 양의 정수로 그래프 G를 몇개로 나눌것인가를 결정한다.
5. v는 그래프 G의 k-way 분할은 공집합이 아니고, 그래프 G의 쌍으로 분리된 부분집합이다. v들의 합집합은 G이다.
분할을 다음을 만족해야한다.
여기서 |x| 표식은 집합 x의 크기이고 x의 모든 원소의 크기의 합과 같다.
분할의 cost는 모든 i,j에 대한 cij의 합이다. 여기서 i와 j는 각각 다른 부분집합이다.
cost는 분할에서 모든 외부 cost를 합한것이다.
분할문제에서는 그래프 G의 분할이 허용할만한 최소 cost를 찾는것을 고려.
크기 1의 노드 n개를 가진 그래프 G는 크기 p의 k개의 부분집합으로 이루어져 있다. kp = m이 성립한다.
아래와 같은 수식을 통해 부분집합을 구성할 경우의 수가 나타난다.
너무 큰 수가 나오기때문에 휴리스틱한 방버으로 솔루션을 찾기 위한것이 이 논문.
1. S는 2n개의 노드를 가진 집합. cost 행렬 C를 따른다.
2. S는 각각 n 개의 노드를 가진 A,B 집합으로 분할된다. 외부 cost T가 최소화 되도록.
이 방법은 임의의 파티션 A,B,S로부터 시작하고 A,B의 부분집합의 교환으로 초기 외부 cost T를 감소시키는 방향으로 진행된
다.
주어진 S와 C에 대해 A*,B*가 최소비용 2Way 파티션이라고 가정하고.
A,B는 임의의 2Way 파티션이다. X,Y는 깨끗한 A,B의 부분집합이고 |X|=|Y| <= n/2 를 만족한다.
X,Y가 교환된 상태를 A*,B*이라고 한다.
문제는 모든 가능한 선택을 고려하지 않고 A,B로부터 X,Y를 정의 하는것이다. 여기에선 순차적으로 그들의 요소를 정의함으로 써 X,Y를 슨사하게 정의 했다.
외부 비용 E는 A의 각 요소에 대해 아래와 같이 정의되고, 내부비용 또한 그렇게 정의 된다.
비슷하게 B에 대해서도 정의 된다.
D는 외부비용과 내부비용의 차이로 아래와 같이 정의되고
1단계 최적화 알고리즘.
g는 비용절감으로 아래와 같이 정의된다.
모든 요소에 대해 D를 계산하고 g가 최대가 되는 a,b를 찾아서 제외한다.
여기서 p값이 n과 같아지면 g를 합산하고 아니라면 p를 증가시키고 Ap,Bp에 대한 D값을 변경한다.
G(g들의 합)이 0보다 작으면 종료하고 아니라면 다시 사이클을 돈다.
효과
임의의 람다값에 대해 람다개의 점의 쌍에 최적 교환을 찾는 것이다. 람다값이 작으면 좋은 교환을 찾기 힘든데, 람다가 증가함에 따라 연산도 빠르게 증가하기 때문이다.
제안한것은 람다 쌍의 최적 교환을 근사하게 순차적으로 찾는것이다. 람다값은 미리 선택되는것이 아니고 가능한 한 큰 개선을 가지게 선택된다. 이 기술은 상당한 속도를 얻기 위해 일정량의 힘을 희생한다.
비용절감의 시퀀스를 구성하고, 최대 일부 합을 구할때, 어떤 g가 음수가 되더라도 종료되지 않는다.
이 뜻은 몇개의 요소만 교환하면 실제 비용이 증가하는 세트를 식별할수 있지만, 전체 집합을 교환하면 순 이익이 발생하는 것을 의미한다.
여러 행렬에 대해 실험을 했으나 비슷한 결과를 봤다.
0이 아닌 원소의 비율이 5~50퍼센트인 0-1행렬.
k=2~10인 동일한 비율로 분산된 정수 요소의 0-k 행렬.
알려진 크기와 결합강도의 군집으로 이루어진 행렬.
그래서 여기에선 요약만 해두었다.
더 자세한 토론은 Ref 3를 참고.
P를 1단계 최적화 솔루션을 이용해 랜덤 시작 파티선에서 전역적인 최적을 찾은 확률이다.
이 확률 p는 30*30의 행렬에서는 0.5, 60*60에서는 0.2~0.3, 120*120 에서는 0.05~0.1 로 나타났다.
함수적으로 표현하면 아래와 같다.
실행시간.
실행시간은 행렬의 크기와 비례하게 증가한다.
다른 크기의 집합에서의 분할.
크기 n의 집합 S를 서로다른 크기 n1,n2로 분할하는 것으로 바꾸는 것은 간단하다. n1<n2일때.
이때 한번의 프로시저에서 교환할수 있는 최대 쌍을 작은쪽인 n1으로 제한한다.
그외 다른 연산은 각 집합의 모든 요소에 대해 수행한다.
파티션 S는 최소 n1개, 최대 n2개를 가지는 부분집합 2개로 이루어져있고, n1+n2 = n을 만족한다.
그러나 부분집합은 다시 지정되지 않는다.
프로시져는 더미 요소를 추가해서 강제 정렬하는 방법으로 쉽게 수정된다.
이 더미들은 어느것과도 연결되지 않은 요소들이다. 행렬 어디에 나타나든 비용이 없는 요소인것이다.
S의 요소가 2n2 가 되게 더미를 추가해서 적용하면 된다.
다른 크기의 요소
같은크기의 요소의 그래프로 가정했었다.
이 문제는 크기 K의 노드를 크기 1의 k개 노드의 클러스터로 적절한 비용의 에지로 변환해서 처리한다.
문제의 크기느 K값에 비례하여 증가하고, 합리적인 범위에서 생성된 노드수를 유지하는데에 조금의 정확도를 희생할 필요가 있다.
Multiple- Way 분할.
1. 2way 문제로 축소.
기본 아이디어는 크기 n의 k개 집합에서 가능한 가까운 최적의 쌍으로 파티션을 만들 부분집합의 쌍을 2way 분할 프로시져 실행을 반복해 한다. 물론 최적쌍은 글로벌 최적성에 필요한 조건일뿐.
1쌍을 전체적으로 최적화 하기위해 3개 이상의 부분집합에서 3개이상의 항목을 복잡하게 교환해야할 경우가 발생하는데, 이것을 순간적으로 발견하는 합리적인 방법은 아직 모름.
실제로는 2개의 부분집합이 최적화 될때 다른 부분집합의 최적성을 변화시킬수 있으므로 더 많은 pass 가 실제로 필요할 것이다.
실험에선 pass 횟수가 적고 프로세스가 빠르게 수렴하는것을 나타낸다. 예로 우리 알고리즘이 i,j를 최적화하기 위한 집합의 다음 쌍으로 선택하면, i나 j는 쌍 i,j가 마지막으로 선택된 이후로 변경된것이다.
이 선택 프로세스를 사용하면, 각 집합 쌍에 대해 pass의 평균 숫자가 n과 k 모두의 천천히 증가하는 함수로 나타난다.
분할 시작.
여기에선 기본 기법을 개조하는걸 기반으로 좋은 시작 파티션을 만드는 방법을 논의한다.
시작 파티션을 정해야하는 주된 이유는 이 방법이 쌍을 최적화 시키는데 필요한 작업량을 줄이기 때문이다.
또한 이 경향을 평가하기 어려워도 최적 솔루션의 확률을 높일 수도 있다.
기본 아이디어는 k-way 시작 파티션 생성을 만든다. r-way를 첫번째로 만들고, 이것은 s-way의 각 결과 부분집합에서 그렇게 t-way까지. (K = r*s*...*t)
이 방법으로 만든 시작 파티션이 임의로 만든것보다 낫다.
이 일반적인 접근은 다음과 같은 어려움을 겪기 쉽다.
첫 분할은 원래의 집합을 가능한 큰 내부 연결을 시도해 r개의 부분 집합으로 나눈다.
이것은 명백하게 각 부분집합을 나누려고 하는 다음 단계와 충돌한다.
두번째 방법은 2.6절에서 설명했던 기본 방법의 수정된 버전을 이용해 kn개 요소의 집합을 n개의 집합, (k-1)n개의 집합으로 분할하는것.
이방법은 2번째 선택의 편향이 첫 집합 식별에서 오류를 만들것이다. 이 현상은 k값이 크고 집합이 작을때 더 심각하다.
부분집합을 순차적으로 끊는 방법은 다른 잠재적 결함이 있다.
시작 구성에 관계 없이 특정 문제에 사용될 때마다 거의 동일한 세트를 식별하므로 하나의 비용행렬에서 두번 사용하면 거의 얻지 못한다.
그러나 쌍 최적화 수행 순서의 변형은 여전히 일반적으로 다른 최종 파티션을 생성할 수 있다.
순차적으로 끊는 방법과 쌍 최적화를 통한 제한된 계산은 임의의 k-way 시작 파티션에 적용된 쌍 최적화의 결과보다 평균적으로 좋은 솔루션을 산출한다
순차적으로 끊는 방법의 실행시간은 직선 쌍 최적화 보다 적다.
확장 요소
앞서 다른 크기의 부분집합에서의 분할을 다루는 방법에서 더미 요소를 추가하는 방법을 언급했었다.
이것은 확장을 허요해서 전반적인 비용을 낮추려는 시도를 한 해법에서 소개할 slack의 의미와 비슷해 보인다.
다음과 같이 최소 비용 솔루션과 이에 상응하는 최적 확장 금액을 찾는 것이 가능합니다.
문제가 kn 점이 각각 n 점의 k 개 세트로 분할되었다고 가정합니다.
여유분없이 시작하면 최적의 할당이 발견됩니다.
여분의 부분 집합을 생성하기에 충분한 n 개의 더미가 추가되어 (k + 1) n 개의 문제를 만드는 식으로 진행됩니다.
결국, 하나의 부분 집합은 전체적으로 더미로 구성된다.
이러한 상황이 발생하면 우리는이 더미 세트가 제거 된 파티션을 최상의 솔루션으로 사용합니다.
댓글