Outranking Algorithms 학습자료
Outranking 알고리즘은 다기준 의사결정 문제에서 대안 간 우선순위를 비교하고 순위를 결정하기 위해 사용되는 방법입니다. 대표적인 outranking 알고리즘에는 ELECTRE와 Promethee가 있으며, 이 자료에서는 ELECTRE 알고리즘의 주요 개념과 사용법을 다룹니다.
1. ELECTRE 알고리즘 개요
ELECTRE(Elimination and Choice Expressing Reality)는 다양한 대안들 간의 선호도나 우선순위를 계산하여 우수한 대안을 선택하는 알고리즘입니다. ELECTRE 알고리즘은 대안 간 비교를 통해 하나의 대안이 다른 대안보다 얼마나 우월한지 평가하는 우월 행렬(outranking matrix)을 생성합니다.
ELECTRE 알고리즘의 종류
- ELECTRE I: 가장 기본적인 버전으로, 우월 행렬을 통해 간단히 대안을 비교합니다.
- ELECTRE II: 우선순위가 다른 대안들을 분류할 수 있으며, 강한 우선순위(strong outranking)와 약한 우선순위(weak outranking)를 구분합니다.
- ELECTRE III: 불확실성과 기준 가중치를 포함하여 보다 정교한 우선순위를 계산합니다.
2. ELECTRE 알고리즘 사용 단계
ELECTRE 알고리즘은 크게 다음과 같은 단계로 진행됩니다.
- 우선순위 문제 정의: 대안, 기준, 성능 테이블, 기준별 척도를 설정합니다.
- Concordance 및 Discordance 지수 계산:
- Concordance 지수: 하나의 대안이 다른 대안보다 얼마나 우월한지를 나타냅니다.
- Discordance 지수: 대안들 간에 어느 정도의 차이가 있는지를 나타냅니다.
- 우월 행렬(outranking matrix) 생성: Concordance와 Discordance 지수를 사용하여 각 대안 간의 우선순위를 나타내는 우월 행렬을 만듭니다.
- 순위 도출: 최종적으로 대안의 순위를 계산하여 최적의 대안을 선정합니다.
3. ELECTRE I: 기본 outranking 계산
ELECTRE I은 가장 기본적인 버전으로, Concordance와 Discordance 지수를 사용해 대안을 평가합니다.
단계별로 ELECTRE I을 실행해 봅시다.
from mcda.matrices import *
from mcda.relations import *
from mcda.scales import *
from mcda.outranking.electre import *
# 대안 및 성능 테이블 설정
alternatives = ["Peugeot 505 GR", "Opel Record 2000 LS", "Citroen Visa Super E", "VW Golf 1300 GLS", "Citroen CX 2400 Pallas"]
scales = {i: QuantitativeScale(1, 5) for i in range(7)}
dataset = PerformanceTable(
[
[4, 2, 1, 5, 2, 2, 4],
[3, 5, 3, 5, 3, 3, 3],
[3, 5, 3, 5, 3, 2, 2],
[4, 2, 2, 5, 1, 1, 1],
[4, 1, 3, 5, 4, 1, 5],
],
alternatives=alternatives,
scales=scales
)
# 가중치와 임계값 설정
W = {0: 0.780, 1: 1.180, 2: 1.570, 3: 3.140, 4: 2.350, 5: 0.390, 6: 0.590}
c_hat = 0.75 # Concordance 임계값
d_hat = {i: 2 for i in range(7)} # Discordance 임계값
# ELECTRE I 인스턴스 생성
electre1 = Electre1(dataset, W, c_hat, d_hat)
# Concordance 및 Discordance 지수 계산
concordance_mat = electre1.concordance()
discordance_mat = electre1.discordance()
# 우월 행렬 생성
outranking_matrix = electre1.outranking(concordance_mat, discordance_mat)해석
Concordance와 Discordance 지수를 기반으로 우월 행렬(outranking matrix)이 생성됩니다. 이 행렬에서 한 대안이 다른 대안보다 우월한 정도를 알 수 있으며, 높은 Concordance 지수는 선호가 높음을 나타내고 Discordance 지수는 차이가 큼을 의미합니다.
4. ELECTRE II: 강한 및 약한 우선순위 도출
ELECTRE II는 두 가지 우선순위를 사용하여 대안의 강한 우선순위와 약한 우선순위를 구분할 수 있습니다.
# Electre II 설정 및 인스턴스 생성
electre2 = Electre2(dataset, W, 0.65, 0.85, d_hat, {c: 1 for c in dataset.criteria})
# 강한 우선순위와 약한 우선순위 계산
strong_outranking, weak_outranking = electre2.construct()
# 강한 우선순위
print(strong_outranking.data)
# 약한 우선순위
print(weak_outranking.data)해석
- 강한 우선순위는 Concordance와 Discordance 지수 모두에서 높은 평가를 받은 경우에 해당합니다.
- 약한 우선순위는 Concordance 지수는 높지만 Discordance 지수가 다소 낮은 경우로, 확신이 덜한 우선순위라고 볼 수 있습니다.
5. ELECTRE III: 불확실성 및 선호도 기준 설정
ELECTRE III은 Concordance 및 Discordance 지수 외에도 불확실성(U), 선호(P), 무관심(I) 기준을 추가로 고려하여 대안 간의 복잡한 비교를 수행할 수 있습니다.
# ELECTRE III 설정
alternatives = ["Peugeot 505 GR", "Opel Record 2000 LS", "Citroen Visa Super E", "VW Golf 1300 GLS", "Citroen CX 2400 Pallas", "Renault Scenic"]
scales = {i: QuantitativeScale(7, 10) for i in range(4)}
dataset = PerformanceTable(
[
[8.84, 8.79, 6.43, 6.95],
[8.57, 8.51, 5.47, 6.91],
[7.76, 7.75, 5.34, 8.76],
[7.97, 9.12, 5.93, 8.09],
[9.03, 8.97, 8.19, 8.10],
[7.41, 7.87, 6.77, 7.23],
],
alternatives=alternatives, scales=scales
)
W = {0: 9.00, 1: 8.24, 2: 5.98, 3: 8.48}
P = {i: 0.50 for i in range(4)} # 선호 차이
I = {i: 0.30 for i in range(4)} # 무관심 차이
V = {i: 0.70 for i in range(4)} # 불확실성 차이
# ELECTRE III 인스턴스 생성
electre3 = Electre3(dataset, W, I, P, V)
# 우월성 점수 계산
credibility = electre3.construct()
print(credibility.data)해석
- 불확실성은 두 대안의 성능이 어느 정도 비슷한지를 나타냅니다.
- 선호 차이(P)는 대안 간의 최소 차이를 설정하여 어느 정도 차이가 있어야 선호도를 확정할 수 있는지 정의합니다.
- 무관심 차이(I)는 차이가 거의 없어서 두 대안을 동일하게 볼 수 있는 범위입니다.
6. 최종 순위 산출 및 해석
ELECTRE III의 경우 오름차순(distillation)과 내림차순(distillation) 방식을 통해 대안의 순위를 정하고 최종 순위를 산출합니다.
# 오름차순 및 내림차순 Distillation
descending_distillate = electre3.distillation(credibility)
ascending_distillate = electre3.distillation(credibility, ascending=True)
# 최종 순위 도출
final_rank = ascending_distillate & descending_distillate
print(final_rank.data)해석
- 오름차순 Distillation은 약한 대안부터 강한 대안으로 순위를 정하는 방식입니다.
- **내림
차순 Distillation**은 강한 대안부터 약한 대안으로 순위를 정하는 방식입니다.
- 최종 순위는 두 방식의 교차점에서 도출되며, 최적의 대안을 결정할 때 사용됩니다.
요약
- ELECTRE I: 기본 outranking 계산으로 간단한 대안 비교.
- ELECTRE II: 강한/약한 우선순위 도출로 세밀한 대안 비교.
- ELECTRE III: 불확실성 및 선호/무관심 기준을 포함한 정교한 비교.
위 예제를 통해 다양한 ELECTRE 알고리즘을 사용하여 다기준 의사결정에서 대안들을 비교하고 최적의 대안을 찾을 수 있습니다.
Outranking Algorithms 학습자료: ELECTRE TRI와 Promethee
이 자료에서는 ELECTRE TRI와 Promethee 알고리즘을 통해 다기준 의사결정 문제를 해결하는 방법을 설명합니다. 각 알고리즘은 여러 기준을 평가하여 대안을 비교하고 순위를 매기기 위한 방법입니다.
1. ELECTRE TRI
ELECTRE TRI는 대안들을 미리 정의된 범주(category)에 할당하는 데 사용됩니다. 범주는 대안의 성능에 따라 "Low", "Medium", "High"와 같은 계층으로 나뉘며, 각 대안이 어느 범주에 속하는지를 결정합니다.
ELECTRE TRI 문제 정의
- 대안(alternatives): 평가할 대안들의 리스트입니다.
- 기준(criteria): 각 대안을 평가하는 데 사용할 기준입니다.
- 프로필(profiles): 각 범주의 기준 성능을 나타내며, 미리 설정된 범주를 정의합니다.
- 가중치(weights), 선호 임계값(preference thresholds), 무관심 임계값(indifference thresholds), 불확실성 임계값(veto thresholds): 기준별로 설정하여 대안 간 비교에 사용됩니다.
ELECTRE TRI 설정 예제
from mcda.matrices import *
from mcda.outranking.electre import ElectreTri
from mcda.scales import QuantitativeScale
from mcda import PerformanceTable
# 기준별 성능 척도 설정
scales = {
0: QuantitativeScale(0, 1),
1: QuantitativeScale(3, 4),
2: QuantitativeScale(1, 2),
3: QuantitativeScale(0, 1),
4: QuantitativeScale(30, 100),
}
# 대안 성능 테이블 설정
dataset = PerformanceTable([
[0.720, 3.560, 1.340, 0.62, 44.340],
[0.8, 3.940, 1.430, 0.74, 36.360],
[0.760, 3.630, 1.380, 0.89, 48.750],
[0.780, 3.740, 1.450, 0.72, 42.130],
[0.740, 3.540, 1.370, 0.73, 36.990],
[0.690, 3.740, 1.450, 0.84, 42.430],
[0.7, 3.280, 1.280, 0.83, 47.430],
[0.860, 3.370, 1.150, 0.8, 80.790],
], scales=scales)
# 기준별 가중치와 임계값 설정
w = {0: 30, 1: 30, 2: 20, 3: 10, 4: 10}
P = {0: 0.05, 1: 0.1, 2: 0.05, 3: 0.1, 4: 8}
I = {0: 0.02, 1: 0.05, 2: 0.02, 3: 0.05, 4: 2}
V = {0: 0.15, 1: 0.6, 2: 0.25, 3: 0.25, 4: 15}
# 프로필 설정 (각 범주의 기준 성능)
profiles = PerformanceTable(
[
[0.750, 3.500, 1.300, 0.730, 42.00],
[0.800, 3.700, 1.370, 0.790, 43.000],
],
alternatives=["p1", "p2"],
scales=scales
)
categories = ["Low", "Medium", "High"]
# ELECTRE TRI 모델 생성
electre_tri = ElectreTri(dataset, w, profiles, I, P, V, lambda_=0.7, categories=categories)ELECTRE TRI 과정
-
우월성(credibility) 계산: 각 대안이 특정 범주와 얼마나 일치하는지를 나타내는 신뢰도를 계산합니다.
credibility = electre_tri.construct() print(credibility.data) -
낙관적 절차(Optimistic Procedure)와 비관적 절차(Pessimistic Procedure): 각 절차는 대안을 범주에 할당하는 다른 방식으로, 낙관적 절차는 상위 범주에 대한 관대한 평가를 하고, 비관적 절차는 보수적으로 평가합니다.
# 낙관적 절차 optimistic_results = electre_tri.exploit(credibility) print(optimistic_results.data) # 비관적 절차 pessimistic_results = electre_tri.exploit(credibility, pessimistic=True) print(pessimistic_results.data) -
직접 할당(Direct Assignment): 대안을 최종 범주에 직접 할당합니다.
# 낙관적 직접 할당 direct_assignment = electre_tri.assign() print(direct_assignment.data) # 비관적 직접 할당 direct_assignment_pessimistic = electre_tri.assign(pessimistic=True) print(direct_assignment_pessimistic.data)
2. Promethee 알고리즘
Promethee 알고리즘은 대안들을 서로 비교하여 순위를 매기는 방법입니다. Promethee I은 대안 간의 부분적인 순서를 제공하고, Promethee II는 완전한 순위를 제공합니다.
Promethee 문제 정의
- 대안(alternatives): 평가할 대안들입니다.
- 기준(criteria): 각 대안을 평가하는 기준입니다.
- 선호 함수(preference functions): 대안 간 비교를 위해 사용되며, 대안 간 차이에 따라 선호도를 부여합니다.
- 가중치(weights): 각 기준의 중요도를 나타냅니다.
Promethee 설정 예제
from mcda import PerformanceTable
from mcda.functions import VShapeFunction
from mcda.outranking.promethee import Promethee1, Promethee2
from mcda.scales import QuantitativeScale
# 대안과 성능 테이블 설정
action_names = ['a1', 'a2', 'a3', 'a4', 'a5']
scales = {i: QuantitativeScale(-5, 5, preference_direction="MAX") for i in range(6)}
dataset = PerformanceTable([
[1, 2, -1, 5, 2, 2], # a1
[3, 5, 3, -5, 3, 3], # a2
[3, -5, 3, 4, 3, 2], # a3
[2, -2, 2, 5, 1, 1], # a4
[3, 5, 3, -5, 3, 3], # a5
], scales=scales, alternatives=action_names)
# 선호 함수 설정 (V-Shape 함수 사용)
preference_func_list = {
0: VShapeFunction(p=1),
1: VShapeFunction(p=4),
2: VShapeFunction(p=3),
3: VShapeFunction(p=1),
4: VShapeFunction(p=2),
5: VShapeFunction(p=2)
}
# 기준별 가중치 설정
W = {0: 0.5, 1: 3, 2: 1.5, 3: 0.2, 4: 2, 5: 1}Promethee 알고리즘 과정
-
Promethee I: 부분적인 순서를 제공하여 대안 간의 강한 우선순위와 약한 우선순위를 결정합니다.
promethee1 = Promethee1(dataset, W, preference_func_list) res = promethee1.rank() print(res) res.plot() -
Promethee II: 모든 대안에 대해 완전한 순서를 제공합니다. 이 방법을 통해 최종 순위를 확인할 수 있습니다.
promethee2 = Promethee2(dataset, W, preference_func_list) res = promethee2.rank() print(res.data) res.plot() -
Promethee GAIA: Promethee GAIA 분석은 대안의 상대적 위치를 시각적으로 분석하여 기준 간의 상관관계 및 대안 간의 위치를 보여줍니다.
gaia = PrometheeGaia(dataset, W, preference_func_list) gaia.plot()
요약
- ELECTRE TRI: 범
주 할당을 통해 대안을 분류하는 데 사용하며, 낙관적/비관적 절차를 제공합니다.
- Promethee I/II: 대안 간의 강한/약한 선호를 통해 부분적 및 완전한 순위를 제공합니다.
- Promethee GAIA: 대안과 기준의 상관관계를 시각적으로 분석합니다.
이러한 outranking 알고리즘을 통해 여러 기준을 고려하여 대안을 평가하고, 최적의 대안을 선택하는 데 활용할 수 있습니다.
SRMP 학습자료: 순위 지정 다기준 의사결정 방법
이 자료에서는 SRMP (Stochastic Rank Marginal Profile) 알고리즘을 다루며, SRMP는 다기준 의사결정에서 대안의 우선순위를 비교하고 최종 순위를 생성하는 데 사용됩니다. SRMP는 성능 테이블과 프로파일을 이용해 대안 간의 선호 관계를 모델링하고 순위를 매깁니다.
SRMP 문제 정의
SRMP를 사용하려면 다음 요소들이 필요합니다.
- 대안(alternatives): 비교 대상이 되는 여러 대안입니다.
- 기준(criteria): 대안의 성능을 평가하는 기준입니다.
- 성능 테이블(performance table): 각 대안이 각 기준에 대해 얼마나 잘 수행하는지 나타내는 데이터입니다.
- 기준별 가중치(criteria weights): 각 기준의 중요도를 설정합니다.
- 프로파일(profiles): 각 대안을 구분할 기준 점수를 포함하여 성능 테이블과 비교할 기준 값들입니다.
- 사전 지정된 순서(lexicographic order): 기준의 평가 순서를 결정합니다.
SRMP 문제 정의 예제
from mcda import PerformanceTable
from mcda.scales import QuantitativeScale, QualitativeScale
from mcda.outranking.srmp import SRMP
from mcda.relations import PreferenceStructure
# 대안 정의
alternatives = ["Fiat 500", "Peugeot 309", "Renault Clio", "Opel Astra", "Honda Civic", "Toyota Corolla"]
# 기준 정의
criteria = ["cost", "fuel consumption", "comfort", "color", "range"]
# 각 기준별 척도 설정 (정량 및 정성 기준 포함)
scale1 = QuantitativeScale(6000, 20000, preference_direction="MIN")
scale2 = QuantitativeScale(4, 6, preference_direction="MIN")
scale3 = QualitativeScale({"*": 1, "**": 2, "***": 3, "****": 4})
scale4 = QualitativeScale({"red": 1, "blue": 2, "black": 3, "grey": 4}, preference_direction="MIN")
scale5 = QuantitativeScale(400, 1000)
# 척도를 기준에 맞게 맵핑
scales = {
criteria[0]: scale1,
criteria[1]: scale2,
criteria[2]: scale3,
criteria[3]: scale4,
criteria[4]: scale5
}
# 성능 테이블 생성
performance_table = PerformanceTable(
[
[9500, 4.2, "**", "blue", 450],
[15600, 4.5, "****", "black", 900],
[6800, 4.1, "***", "grey", 700],
[10200, 5.6, "****", "black", 850],
[8100, 5.2, "***", "red", 750],
[12000, 4.9, "****", "grey", 850]
],
alternatives=alternatives,
criteria=criteria,
scales=scales
)
# 기준별 가중치 설정
criteria_weights = {
criteria[0]: 1,
criteria[1]: 2,
criteria[2]: 3,
criteria[3]: 2,
criteria[4]: 4
}
# 프로파일 설정 (각 범주별 기준 성능)
profiles = PerformanceTable(
[
[15000, 5.5, "**", "grey", 500],
[10000, 5, "***", "black", 700],
[7000, 4.5, "****", "blue", 900],
],
criteria=criteria,
scales=scales
)
# 사전 지정된 순서 설정 (lexicographic order)
lexicographic_order = [2, 0, 1]
# SRMP 모델 생성
srmp = SRMP(performance_table, criteria_weights, profiles, lexicographic_order)SRMP 순위 지정 과정
-
선호 관계 생성: SRMP 모델은 선호 관계를 기반으로 대안 간 우열을 설정합니다.
preference_matrices = srmp.construct() print(preference_matrices[0].data) print(preference_matrices[1].data) print(preference_matrices[2].data) -
순위 지정(Ranking): 생성된 선호 관계를 이용하여 각 대안의 최종 순위를 결정합니다.
rank = srmp.exploit(preference_matrices) print(rank.data) rank.plot() -
직접 순위 생성(Direct Ranking): 필요에 따라 SRMP 객체를 통해 직접 순위를 생성할 수 있습니다.
rank = srmp.rank() print(rank.data) rank.plot() -
시각화(Plotting): SRMP 모델의 입력 데이터를 시각화하여 비교를 위한 그래프를 생성할 수 있습니다.
# 전체 데이터 시각화 SRMP.plot_input_data( performance_table, srmp, xticklabels_tilted=False, annotations=True, scales_boundaries=False, # 가독성 향상 annotations_alpha=0.5, figsize=(10, 8), ) -
대안 간 비교: 특정 대안들 간의 비교도 가능하며, 동일한 범위에서 그래프를 생성하여 시각적으로 비교할 수 있습니다.
SRMP.plot_input_data( PerformanceTable( performance_table.data.loc[["Fiat 500", "Renault Clio"]], scales=scales ), srmp, xticklabels_tilted=False, annotations=False, scales_boundaries=True, # 동일 범위로 그래프 설정 )
SRMP 학습 (Training SRMP Model)
SRMP 모델은 학습을 통해 다양한 선호 관계를 반영할 수 있으며, 주어진 선호 관계에 기반하여 대안의 순위를 학습합니다.
학습용 선호 관계 정의
먼저, 학습에 사용할 선호 관계를 정의합니다. 예를 들어, 아래와 같이 대안 간의 선호도를 설정합니다.
from mcda.relations import PreferenceStructure, P, I
relations = PreferenceStructure([
P("Fiat 500", "Honda Civic"),
P("Toyota Corolla", "Opel Astra"),
P("Fiat 500", "Renault Clio"),
P("Honda Civic", "Toyota Corolla"),
I("Opel Astra", "Peugeot 309"),
I("Renault Clio", "Honda Civic"),
])
relations.plot()SRMP 모델 학습
선호 관계를 기반으로 SRMP 모델을 학습합니다. 아래 예제에서는 SRMP 학습기를 사용하여 SRMP 모델을 생성합니다.
from mcda.outranking.srmp import SRMPLearner
learner = SRMPLearner(
performance_table,
relations,
max_profiles_number=3,
non_dictator=True,
gamma=0.01
)
# SRMP 모델 학습 및 생성
srmp = learner.learn()
print(srmp.__dict__, learner.fitness)
# 프로파일 데이터 확인
print(srmp.profiles.data)
# 최종 순위 출력
rank = srmp.rank()
print(rank.data)
rank.plot()학습된 SRMP 모델을 통해 직접 순위를 생성할 수도 있습니다.
srmp = SRMP.learn(
performance_table,
relations,
max_profiles_number=3,
non_dictator=True,
gamma=0.01,
)
rank = srmp.rank()
rank.plot()요약
- SRMP는 성능 테이블과 기준 가중치, 프로파일을 기반으로 대안의 순위를 계산합니다.
- 선호 관계를 이용하여 대안 간 비교를 설정하고, 이를 통해 대안의 우월성을 평가합니다.
- SRMP 학습은 주어진 선호 관계에 맞춰 최적의 SRMP 모델을 생성하고 이를 통해 대안을 평가합니다.
SRMP는 다기준 의사결정에서 대안의 우선순위를 분석하고 최적의 대안을 찾는 데 매우 유용한 방법론입니다.
