متدهای به کار گیری الگوریتم ژنتیک در پیشبینی لینک(قسمت چهارم)

در شکل زیر با استفاده از مدل ما، به درستی به سه اجتماع بخش‌بندی شود و مقدار تابع عینی 1 است.

                                          

زمانیکه d_j,c=1 باشد، لینک e_j به اجتماع P_c تخصیص داده می‌شود در غیر این صورت، لینک e_j به اجتماع P_c تخصیص نمی‌یابد. ماتریکس D می‌تواند از ماتریکس B بر طبق معادله‌ی زیر محاسبه شود:

                                                  

شبکه با استفاده از ماتریکس وقوع R، ماتریکس مجاورت لینک A و ماتریکس مجاورت لینک سنگین Q نشان داده می‌شود. ماتریکس مجاورت لینک A می‌تواند توسط معادله‌ی A=R^TR محاسبه شود. در A، عناصر قطری 2 هستند و عناصر غیرقطری مقادیری را در {1، 0} به خود می‌گیرند تا نشان دهند که آیا دو لینک یک گره مشترک دارند یا نه. فرض کنیم که Z یک ماتریکس قطر می‌باشد که عناصر قطری آن معکوس درجه‌های گره هستند یک درجه‌ی گره تعداد لینک‌های متلاقی با آن است به عبارت دیگر:

                                        

ماتریکس مجاورت لینک سنگین به عنوان Q=R^TZR تعریف می‌شود که به معنای احتمال رفتن یک عابر تصادفی از یک لینک به یکی از لینک‌های مجاورش از طریق گره مشترک‌شان می‌باشد. این احتمال می‌تواند به عنوان احتمال تعلق دو لینک مجاور به اجتماع یکسان در نظر گرفته شود.

توابع اصلی GA (الگوریتم ژنتیک)

ورودی: تعداد گره‌های N و تعداد لینک‌های M از شبکه و حداکثر تعداد اجتماعات K را وارد کنید. ماتریکس رویداد R، ماتریکس مجاورت لینک A=R^TR و ماتریکس مجاورت سنگین Q=R^TZR را

محاسبه کنید. تعداد اشخاص U، دوره ماکسیسم T، احتمال تغییر P و پارامترهای SOM (آغاز پیام) یعنی α , β , θ را شرح دهید.

خروجی. ماتریکس بخش‌بندی لینک D* و مقدار تناسب آن H* (یعنی مقدار تراکم بخش‌بندی لینک) و ماتریکس بخش‌بندی گره F را خروجی می‌دهد. بر طبق D* و F شبکه را به اجتماعات بخش‌بندی کنید.

ارزش آغازی: t=0 به طور تصادفی یک جمعیت اولیه B_u(t), …, B₂(t), B₁(t) ایجاد کنید و مقادیر اولیه D* و T* را شرح دهید.

مرحله 1. تناسب جمعیت: برای تمام افراد در جمعیت B_u(t), …, B₂(t), B₁(t) ماتریکس‌های D_u(t), …, D₂(t), D₁(t) و مقادیر متناسب آن‌ها H_u(t), …, H₂(t), H₁(t) را محاسبه کنید.

مرحله 2: دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را بر طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزم‌های دسته‌بندی شده، B₁(t) ,B₂(t) , … , B_u(t) هستند که در آن H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) می‌باشد.

اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) خواهد بود.

اگر t=T باشد، متوقف شوید. D* و H* را خروجی کنید و ماتریکس F متناظر با آن را برای بخش‌بندی گره محاسبه کنید. در غیر این صورت به مرحله 3 بروید.

مرحله‌ی 3. تعویض جمعیت: برای 

فرض کنید که  باشد و برای ایجاد دو شخص موقت (ماتریکس‌های) w_i(t) و  آن‌ها را تعویض کنید. اگر U یک عدد فرد باشد، اینگونه فرض کنید که w_u(t)=B_u(t)

مرحله‌ی 4: تغییر جمعیت: به طور تصادفی اشخاص موقت P^U را انتخاب کنید و عملیات تغییر را بر روی هر شخص موقت انجام دهید.

مرحله 5: SOM (آغاز پیام) جمعیت: برای هر شخص موقت، عملیات آغاز پیام را انجام دهید.

مرحله 6: هنجارسازی جمعیت: هنجارسازی را برای هر شخص موقت انجام دهید. اشخاص هنجارشده را با استفاده از B₁(t+1) ,B₂(t+1) , … , B_u(t+1) مشخص کنید. t=t+1 در نظر بگیرید و به مرحله‌ی 1 بروید.

ماتریکس بخش‌بندی و ارزیابی تناسب برای هر شخص Bi، ماتریکس بخش‌بندی Di را طبق فرمول 14 محاسبه کنید. برای هر اجتماع Ps، 1≤S≤K فرض کنید که Di(:,S)، ستون Sام از ماتریکس Di 

باشد. سپس Ei(s)=R.Di(:,S) یک بردار ستونی است که عوامل آن اعداد صحیح غیرمنفی هستند. یک عامل غیرصفر در Ei(s) نشان می‌دهد که گره متناظر به ei(j,s)≥1 تعلق دارد. Fi(j,s)=1 به این معناست که گره Vj به اجتماع Ps تعلق دارد. تناسب مشخص Bi می‌تواند توسط معادله‌ی زیر محاسبه شود.

                                                                            

از آنجا که اغلب یک مقدار حداکثر در هر ردیف ماتریکس B وجود دارد، ما اغلب با استفاده از فرمول (14)، یک لینک را به یک و فقط یک اجتماع بخش‌بندی کنیم. زمانی که یک لینک، لینک مشترک بین دو اجتماع باشد، نمی‌تواند توسط فرمول 14 به طور مستقیم تشخیص داده شود.

برای تشخیص دو لینک مشترک به طور صحیح، ما می‌توانیم فرمول 14 را با استفاده از فرمول زیر یعنی فرمول 15 جایگزین کنیم.

                                                                            

با استفاده از فرمول 15، یک لینک مشترک می‌تواند به بیش از یک اجتماع بخش‌بندی شود. دسته‌بندی جمعیت B₁(t) ,B₂(t) , … , B_u(t) را طبق مقادیر تناسب‌شان به صورت نزولی دسته‌بندی کنید. فرض کنید که کروموزوم‌های دسته‌بندی شده B₁(t) ,B₂(t) , … , B_u(t) هستند که H₁(t) ≥ H₂(t) ≥ … ≥ H_u(t) است. اگر H₁(t)>H* باشد، D*=D₁(t) و H*=H₁(t) است.

تعویض جمعیت: برای  عملیات تعویض با استفاده از قوانین زیر بر روی s  انجام دهید. به طور تصادفی ستون s را انتخاب کنید ستون sام از   را با استفاده از ستون sام B_i(t) اصلاح کنید و دو فرد موقت w_i(t) و  را به دست آورید. فرض کنید که w_i(t)=