روش تبادل و جانشینی

یکی از روشهای حل مسائل چند هدفه که در حین حل مسئله، اطلاعاتی از تصمیم گیرنده دریافت می شود روش تبادل و جایگزینی می باشد. این روش برای اولین بار توسط ”هی مز“ در سال 1975 به منظور بکارگیری در سیستم های منابع آب، مطرح گردید.

پس از آن محققان بکارگیری این روش را به منظور حل مدل های چند هدفه در زمینه های دیگر نظیر سیستم های حمل و نقل پیشنهاد نمودند.یکی از مهمترین ویژگی های این روش آن است که، برای توابع با مقیاس های مختلف کاربرد دارد.

---

روش تبادل و جانشینی چیست؟

این روش به دنبال تعیین ضرایب ترجیحات تصمیم گیرنده است و نشان می دهد که تصمیم گیرنده به چه میزان هدف Fl  را به یک واحد هدف F_i ترجیح می دهد.

در سال‌های اولیه، روش تبادل و جانشینی بیشتر در حوزهٔ بهینه‌سازی ترکیبی (Combinatorial Optimization) مورد استفاده قرار گرفت؛ اما با پیشرفت‌های بعدی در الگوریتم‌های هوش مصنوعی و برنامه‌ریزی ریاضی، این روش به‌سرعت در صنایع مختلف از جمله خودروسازی، انرژی، بهداشت و درمان و زنجیره تأمین گسترش یافت.

از نظر نظری، روش تبادل و جانشینی بر این اصل استوار است که هدف نهایی تصمیم‌گیرنده، یافتن ترکیبی از گزینه‌ها و معیارهاست که حداکثر رضایت کلی (Overall Satisfaction) را فراهم کند؛ این رضایت با استفاده از یک تابع هدف ترکیبی که شامل اجزای تبادل و جانشینی است، محاسبه می‌شود.

روش تبادل و جانشینی (SWT) شامل دو مرحله اصلی است :

• توابع تعدیل Trade off Function
  • محاسبه جداگانه جواب ایده ال هریک از اهداف و ایجاد راه حل موثر با حل مدل جدید
• توابع ارزش ضمیمه Surrogate worth Function
  • تجسس برای انتخاب یک راه حل ارجح ،از بین راه حل های موثری که از مجموعه ای از توابع ارزشی ضمیمه بدست آمده است.

---

مراحل اجرای روش تبادل و جایگزینی

جواب های بهینه را برای هر هدف به صورت جداگانه بدست آورید و یکی از اهداف را به دلخواه انتخاب کرده و مدل جدیدی را بر اساس ورود سایر توابع هدف به عنوان محدودیت ایجاد نموده و پس از تنظیم تابع دوگان لاگرانژ برای مدل فوق ، جواب های موثر را بدست آورید. این مرحله در واقع همان مرحله تبادل یا Trade off می باشد که در آن توابع تعدیل تعیین می گردد.

تابع ارزشی ضمیمه

را از طریق تعامل متقابل با تصمیم گیرنده، ارزیابی کرده و راه حل های مربوط به دامنه بی تفاوتی تصمیم گیرنده را مشخص نمائید. راه حل ترجیح داده شده توسط تصمیم گیرنده ، راه حل بهینه برای مسئله اصلی خواهد بود که در واقع این مرحله نیز مربوط به Surrogate worth می باشد.

تابع تعدیل

تحت شرایطی که توابع هدف و محدودیت ها به صورت زیر باشند :

max fi(x)

S.t:  gj(x)≤ 0 ; j= 1,2,…..,m

      xi≥ 0

ابتدا بر اساس محدودیت های موجود و با توجه به هر یک از توابع هدف ، بصورت جداگانه محاسبات را انجام داده و برای هر یک از آنها *f*, x1*, x2 ,…. را تعیین می نمائیم. سپس یکی از اهداف را به دلخواه ، نظیر هدف اول ، انتخاب نموده و سایر هدفها را به صورت محدودیت نشان میدهیم:

Max f1(x)

S.t: fi(x) ≥ εi ; i= 2,…..,k

gj(x)≤ 0 ; j= 1,2,…..,m

xi≥ 0

((در این مثال با توجه به آنکه هدف اول انتخاب شده و سایر اهداف به عنوان محدودیت تلقی گردیده اند ،i مربوط به سایر اهداف از هدف 2 شروع شده است.))

توابع هدفی که به صورت محدودیت نشان داده شده اند ، بزرگتر یا مساوی مقدار εi خواهند بود. بطوری که اگر *fi راه حل ایده آل هدف iام و *εi انحراف قابل قبول از راه حل ایده آل *fi باشد ،εi که به صورت پارامتریک است بشکل زیر محاسبه می گردد:

εi= fi*(x) – εi* ,  εi*> 0

با بکارگیری تابع دوگان لاگرانژ که بر اساس توابع هدف و محدودیت ها به صورت زیر خواهد بود، می توان مسئله را حل نمود :

L(x,u,λ)=f1(x)+∑λ1i(fi(x)-εi)- ∑ujgj(x)

بطوری که :

i= 2…….k   ,       j=1………m

Uj ≥ 0 , λ1i

 بر طبق قوانین ”کان تاکر“ در نقطه بهینه از تابع مورد نظر باید دو مورد زیر در نظر گرفته شود :

λ1i(fi(x)-εi )= 0

λ1i ≥ 0 ; i=2,3,…..,k

و همچنین بر اساس شرایط کان – تاکر بایستی :

L/∂Xi=0∂

Uj gj(x) = 0

بدین ترتیب می توان مجموعه ای از راه حلهای موثر را بدست آورد و وارد مرحله دوم شد.

(( در بحث توابع تعدیل λli مشخص کننده ارزش سایه ای برای تابع هدف lام به ازائ هر واحد تغییر در e_i می باشد به همین دلیل به عنوان یک محدودیت الزامی حائز اهمیت ست.))

---

مثال توابع تعدیل Trade off Function

Max:f1(x)=x1.x2

Min:f2(x)= (x1-4)²+x2²

S.t:  x1+x2≤ 25  :  g1

X1 , 2 ≥ 0

 بدین ترتیب ابتدا راه حل ایده آل هر یک از توابع هدف را ( در این مسئله دو تابع هدف ) بدست می آوریم. بر این اساس داریم :

F1*= 156.25   //  X1*= X2* = 12/5   F2* = 0       //   X1*= 4  ,    X2* = 0

سپس با انتخاب یکی از اهداف به دلخواه ،مدل جدید را تعیین می کنیم:

Max: f1(x)= x1.x2

S.t: -(x1-4)²-x2² ≥ ε2 = -C

x1+x2≤ 25  :  g1

X1 , X2 ≥ 0

توجه نمائید که :

ε2= f2*(x) – ε2*

و چون جواب ایده آل هدف دوم برابر با صفر است، در نتیجه:

0- ε2*=-C          ->     ε2*=C

لاگرانژین مسئله به صورت زیر است :

L= x1.x2 ++ λ12{-(x1-4)²-x2²+ C }- u1 {x1+x2– 25}

و همچنین :

L/∂X1=x2– 2λ12 ( x1 – 4) – u1= 0∂

L/∂X2=X1– 2λ12 x2 – u1= 0∂

U1g1(x)= u1 .( x1+x2– 25)=0

λ1i(fi(x)-εi )= λ12{-(x1-4)²-x2²+ C }=0

• در این مثال u1 .( x1+x2– 25)=0 که یا بایستی u1 برابر با صفر باشد و یا (25-x2+x1) برابر با صفر باشد و با توجه به محدودیت f2(x) ≥ ε2 ، اگر (25-x2+x1) برابر با صفر باشد،شرط مربوط به محدودیت f2(x) ≥ ε2 رعایت نخواهد شد ، بنابراین، در این مثال u1 برابر با صفر می باشد.
• λ12 بزرگتر از یک می باشد ، پس نتایج به صورت زیر خواهد بود:

λ1i=x2 ÷[ 2(x1-4)] = x1 ÷ 2x2

X2=√x₁ (x1 – 4)

(x1-4)²+x2² = C

• با توجه به محاسبات بالا [(λ1i=x2 ÷[ 2(x1-4)]  ،مقدار X1 بایستی بزرگتر از 4 باشد وگرنه مخرج کسر منفی یا صفر خواهد شد .و بر اساس λ1i= x1 ÷ 2x2 ،  مقدار x2 بایستی بزرگتر از صفر باشد ، وگرنه مخرج کسر صفر خواهد شد و چون λ12  نیز بزرگتر از یک است ، می توان نتیجه گرفت:                    x2>0 , x1>4

بدین ترتیب با جایگذاری موارد مذکور در معادلات بدست آمده می توان جدول زیر را تهیه نمود:

ردیف اول) X2=√X1(x1 – 4) → X1=5 → X2 = 2.24     λ1i=x2 ÷[ 2(x1-4)] → 2.24 ÷ [2(5-4)]=1.118  →3.46 ÷[2(6-4 )]=0.866

x1	x2	λ12	f1	f2
5	2.24	1.118	11.18	6
6	3.46	0.866	20.78	16
7	4.58	0.764	32.06	29.97
8	5.65	0.707	45.20	47.92
9	6.7	0.671	60.3	69.89
10	7.75	0.645	77.46	96
11	8.77	0.627	96.47	125.91
12	9.8	0.612	117.58	160
13	10.82	0.601	140.61	198

λ₁₂ بدست آمده در جدول بالا نشان دهنده مقدار هدف 2 است که قابل جایگزین با یک واحد هدف 1 می باشد. و یا بطور کلی λ_li مقدار هدف l است که قابل جایگزین با یک واحد هدف i می باشد ، چرا که اگر مشتق تابع لاگرانژ را نسبت به iε نشان دهیم،خواهیم داشت :

L/∂εi=- λli∂

بجای L ∂ می توان fl(.) ∂ را جایگزین نمود در آن صورت خواهیم داشت :

fl(.)/∂εi=- λli∂

و چون محدودیت0< λ₁₂ وجود دارد ، تحت شرایط  λ1i(fi(x)-εi)=0 ، بایستی fi(x)-εi)=0) باشد .در نتیجه  fi(x)=εi

در fl(.)/∂εi=- λli∂ میتوان fi(.)∂ را جایگزین ∂εi نمود . بنابر این خواهیم داشت :

fl(.)/∂fi(.)=λli∂-

لذا λli مقدار هدف l است که قابل جایگزین با یک واحد هدف i می باشد.

---

مثال تابع ارزشی ضمیمه

در این مرحله باید از ترجیحات تصمیم گیرنده در ارتباط با تعدیل هر یک از اهداف نسبت به یک واحد از هدف دیگر( تحت شرایطی که سایر اهداف ثابت باشند)، مطلع شد و سپس ارجحیت های تصمیم گیرنده را بر روی یک مقیاس رتبه ای مدرج نمود. این مقیاس می تواند از اعدادی بین 10+ و 10- تشکیل شده باشد. بطوری که صفر مرکز بی تفاوتی برای تصمیم گیرنده خواهد بود.ارجحیت های اعلام شده توسط تصمیم گیرنده تابع ارزشی ضمیمه را تشکیل می دهند.

تابع ارزشی ضمیمه تابعی از نرخ تعدیل است که با (W_li) نشان داده می شود بطوری که :

• اگر تعدیل λ_li واحد از fl بر یک واحد fi ترجیح داده شود :  W_li>0
• اگر تعدیل λ_li واحد از fl بر یک واحد fi ترجیح داده نشود : W_li<0
• اگر تعدیل λ_li واحد از fl بر یک واحد fi بی تفاوت باشد :   W_li=0

بدین ترتیب بایستی دامنه بی تفاوتی از تابع ضمیمه ((W_li(λ_li)) تعیین گردد. با توجه به مثال ذکر شده ، ارجحیت های تصمیم گیرنده بر روی مقیاس 10 الی 10- را به صورت زیر می توان نشان داد:

x1	x2	λ12	f1	f2	w12
5	2.24	1.118	11.18	6	10+
6	3.46	0.866	20.78	16	9+
7	4.58	0.764	32.06	29.97	7+
8	5.65	0.707	45.20	47.92	5+
9	6.7	0.671	60.3	69.89	2+
10	7.75	0.645	77.46	96	0
11	8.77	0.627	96.47	125.91	1-
12	9.8	0.612	117.58	160	7-
13	10.82	0.601	140.61	198	10-

بر اساس اطلاعات موجود در جدول و با ملاحظه نمودار ، مشخص است که ارجحیت تصمیم گیرنده به ازائ 77.46 برای هدف اول و با 96 برای هدف دوم و به ازائ لاندای معادل 0.645 در نقطه بی تفاوتی است. (0= w12) یعنی: W12(λ*12=0.645)=0 و راه حل نهایی عبارت است از : X1*=10 X2*=7.75

روش تبادل و جایگزینی چند هدفه

تحت شرایطی که بیش از دو هدف وجود داشته باشد، تمام مراحل ذکر شده را برای سایر اهداف انجام داده و راه حل های مربوط به دامنه بی تفاوتی را تعیین می نمایند. در آن صورت برای تابع هدف مسئله خواهیم داشت :   {F*={f*1 , f*2 , …..f*k  بطوری که راه حل های بهینه بدست آمده بر اساس : Wli(λli)=0

حال با توجه به موارد بالا باید بتوان از بین راه حل های بدست آمده راه حل موثر را بدست آورد بطوری که با حل مدل بهینه زیر می توان جواب های نهائی را بدست آورد.

Max fl(x)

S.t: fi(x) ≥ f i * (x) ; i= 1,2,…..,k

gj(x)≤ 0 ; j= 1,2,…..,m

xi≥ 0

گاهی ممکن است به راه حل عملی که در آن تابع ضمیمه برابر با صفر است ،دست نیابیم در آن صورت بصورت تقریبی تابع ضمیمه صفر را پیدا کرده و یا بر اساس روش رگرسیون ابتدا معادله خط مربوط به کلیه توابع ضمیمه را تعیین و بر اساس آن راه حل عملی را برای تابع ضمیمه صفر ،بدست می آوریم.

---

مزایا روش تبادل و جانشینی

1. انعطاف‌پذیری وزن‌ها: وزن‌های معیارها به‌صورت پویا و بر پایهٔ نتایج تبادل به‌روزرسانی می‌شوند؛ بنابراین، روش تبادل و جانشینی می‌تواند به‌سرعت با تغییرات محیطی سازگار شود.
2. بهبود دقت ارزیابی: تبادل اطلاعات بین گزینه‌ها باعث می‌شود تا داده‌های ناقص یا نادقیق با اطلاعات دیگر تکمیل شوند و ارزیابی نهایی دقیق‌تر باشد.
3. قابلیت استفاده در مسائل بزرگ: با استفاده از الگوریتم‌های تبادل کارآمد (مانند تبادل مبتنی بر گرادیان)، این روش می‌تواند به‌سرعت بر روی مجموعه‌های بزرگ گزینه‌ها و معیارها اجرا شود.
4. قابلیت ترکیب با هوش مصنوعی: می‌توان الگوریتم‌های یادگیری ماشین را برای پیش‌بینی وزن‌های به‌روز شده یا بهینه‌سازی تبادل استفاده کرد؛ این ترکیب باعث ارتقای عملکرد روش تبادل و جانشینی می‌شود.

معایب روش تبادل و جانشینی

1. نیاز به داده‌های دقیق: اگر داده‌های اولیه (مقادیر معیارها) دارای خطا یا عدم قطعیت زیاد باشند، تبادل اطلاعات ممکن است منجر به گسترش خطاها شود.
2. پیچیدگی تنظیم پارامترها: انتخاب پارامترهای تبادل (مانند نرخ تبادل یا تعداد دوره‌های جانشینی) می‌تواند بر نتایج تأثیر قابل‌توجهی داشته باشد و نیاز به تنظیم دقیق دارد.
3. حساسیت به وزن اولیه: اگر وزن‌های اولیه به‌درستی تعیین نشوند، فرآیند جانشینی ممکن است به‌سوی یک مسیر نادرست هدایت شود؛ بنابراین، استفاده از روش‌های وزن‌دهی ترکیبی توصیه می‌شود.
4. نیاز به محاسبات زیاد در مسائل بسیار بزرگ: در مسائلی که تعداد گزینه‌ها و معیارها به‌صورت صدها یا هزاران باشد، محاسبهٔ ماتریس تبادل و به‌روزرسانی وزن‌ها می‌تواند زمان‌بر باشد؛ در این موارد استفاده از پردازش موازی یا الگوریتم‌های تقریب‌نویسی ضروری است.

---

توسعه‌های اخیر در روش تبادل و جانشینی

در سال‌های اخیر، پژوهشگران تلاش‌های زیادی برای توسعه و بهبود روش تبادل و جانشینی انجام داده‌اند. یکی از مهم‌ترین توسعه‌ها، ترکیب این روش با روش‌های یادگیری تقویتی (Reinforcement Learning) است. در این رویکرد، یک عامل یادگیری تقویتی آموزش داده می‌شود تا به‌صورت خودکار پارامترهای تبادل را تنظیم کند و بهترین استراتژی تبادل را برای هر مسئله پیدا کند.

توسعهٔ دیگر، استفاده از روش تبادل و جانشینی در مسائل تصمیم‌گیری گروهی است. در این مسائل، نظرات چندین تصمیم‌گیرنده باید با هم ترکیب شوند. روش تبادل و جانشینی می‌تواند با استفاده از روش‌های تجمیع نظرات، به یک تصمیم‌گیری جمعی منسجم و قابل‌قبول کمک کند.

همچنین، پژوهشگران در حال بررسی استفاده از روش تبادل و جانشینی در مسائل تصمیم‌گیری پویا هستند. در این مسائل، شرایط محیطی به‌طور مداوم تغییر می‌کنند و تصمیم‌گیرندگان باید به‌طور مداوم تصمیمات خود را به‌روز کنند. روش تبادل و جانشینی می‌تواند با استفاده از مدل‌های پیش‌بینی و تحلیل سناریو، به تصمیم‌گیری‌های پویا و سازگار کمک کند.

نتیجه‌گیری

روش تبادل و جانشینی به عنوان یک رویکرد نوین و انعطاف‌پذیر در حوزه تصمیم‌گیری چندمعیاره، با ترکیب ایده‌های تبادل اطلاعات و جانشینی معیارها، امکان ارزیابی دقیق‌تر و سازگارتر را فراهم می‌کند. این روش با قابلیت تطبیق با شرایط متغیر و ترکیب با تکنیک‌های هوش مصنوعی، می‌تواند در طیف گسترده‌ای از صنایع و کاربردها به‌کار رود.

در این مقاله، به بررسی جامع روش تبادل و جانشینی پرداختیم؛ از مفاهیم پایه و مراحل اجرا تا کاربردها، مزایا، معایب و چالش‌های آن. همچنین، به مقایسه این روش با سایر روش‌های تصمیم‌گیری چندمعیاره و توسعه‌های اخیر در این زمینه پرداختیم.

با تسلط بر این روش، دانشجویان و پژوهشگران می‌توانند در حل مسائل پیچیده و بهبود فرآیندهای تصمیم‌گیری نقش مؤثری ایفا کنند و به سازمان‌ها و صنایع کمک کنند تا تصمیمات بهینه‌تری اتخاذ کنند.

---

سوالات متداول (FAQ)