مقاله ترسیم گراف در چند ضلعی حفره دار توسط الگوریتم ژنتیک

بخشی از مقاله

ترسیم گراف در چند ضلعی حفره دار توسط الگوریتم ژنتیک

چکیده:
با توجه به اهمیت زیاد مساله ترسیم گراف و کاربردهای آن(به عنوان مثال در مهندسی نرم افزار، واسـط هـای

گرافیکی)، این مساله مورد توجه فراوان واقع شده است و تحقیقات مختلفی بر روی مساله ترسیم انواع گـراف
ها صورت گرفته است.از جمله این مقالات ، ترسیم گراف در چندضلعی ها، ترسیم گـراف مسـطح در درون

یک چندضلعی، ترسیم یک درخت درون چند ضلعی است .

یکی از مسائل مربوط به ترسیم گراف همانطور که در بالا اشاره شد مساله ترسیم گراف مسطح در درون یک چندضلعی است که قبلا الگوریتمی برای حل مساله ارائه شده است. اما در بعضی کاربردها نیاز است که گراف مسطح را درون یک چندضلعی حفره دار ترسیم کنیم. با توجه به این موضوع که ترسیم گـراف در چندضـلعی حفره دار تاکنون پیاده سازی نشده است ما در این مقاله دو روش برای این مساله پیشنهاد کردیم که هر یـک از این دو روش مزایا و معایب خاص خود را داراست و در کاربردهای متفاوت می توان از هـر یـک از آن هـا بهره برد. یکی از روش ها گراف مسطح را طوری ترسیم می کند که مکان اولیه گره ها تغییـر نمـی یابنـد و بـا ایجاد خم ها از برخورد بین یال ها جلوگیری می کند. ولی در روش دیگر موقعیـت گـره هـا ثابـت نیسـت و الگوریتم با توجه به قیدها و اولویت ها مکان گره ها را مشخص می کند. در این روش هیچ خمی بـه یـال هـا

داده نمی شود.

واژه هـــای کلیـــدی: الگـــوریتم ژنتیـــک، ترســـیم گـــراف، چندضـــلعی حفـــره دار

-1 مقدمه
گراف ساختاری انتزاعی است که برای مدل کردن اطلاعاتی مانند نمایش اشیاء و روابط بین این آن ها بکار مـی رود کـاربرد دارد.
ترسیم گراف عبارت از نمایش هندسی اطلاعاتی که به صورت گراف مدل شده اند، اسـت1]و.[2بـه عنـوان مثـال بـرای نمـایش

سلسله مراتب و ارتباطات اجزاء شبکه های کامپیوتری می توان از گراف استفاده کرد. یک گـراف بـدون جهـت را معمـولا بـا دو مجموعه G  (V , E) که V مجموعه راس ها و E زوج مرتبی از مجوعه V V اسـت. مـانع اصـلی بـرای نمـایش یـک گراف به صورت گرافیکی نحوه تبدیل حالت غیر گرافیکی گراف به صورت گرافیکـی تعریـف یـک معیـار خـوب بـرای نمـایش

است.برای مثال توزیع یکنواخت گره ها، فاصله بیشینه گره ها از یکدیگر،طول یکنواخت یال ها، تعداد کم تلاقی بین یال هـا و در

صورت امکان تقارن و تطابق با صفحه نمایش3]و4و5و.[6 با آنکه مساله ترسیم گـراف در چندضـلعی هـا کـاربرد فراوانـی دارد
تحقیقات اندکی در این زمینه صورت گرفته است.[7] اغلب الگوریتم های ترسیم، گراف را در یک صـفحه نامحـدود ترسـیم مـی کنند 8]و9و11و11و12و 13و14و15و16و17و.[ 18 و تعداد کمی الگوریتم برای ترسیم گراف در چند ضلعی ارائه شده است. ولی با توجه به اینکه کاربردهایی وجود دارد که لازم است گراف مسطح را در چندضلعی حفره دار ترسیم کند. تاکنون الگـوریتمی برای ترسیم گراف در چندضلی حفره دار ارائه نشده است. چون این یـک مسـاله Np-complete اسـت 19]و21و21و.[22 بـا

آنکه روش های مختلفی برای ترسیم درخت ها یا گراف ها درون انواع چندضلعی ها ارائه شده است 1]و[23 اما تاکنون روشـی

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

-2 ترسیم گراف مسطح در چند ضلعی حفره دار توسط الگوریتم اول

در این الگوریتم ابتدا یال های گراف به صورت زوج مرتب و همینطور موقعیت اولیه گره های گراف به عنـوان ورودی الگـوریتم دریافت می شود. سپس این الگوریتم با تعویض موقعیت گره ها (به عنوان مثال تعویض موقعیت گره 2 با گره 5 گراف) سعی می

کند تا گراف را طوری ترسیم کند که معیارهای ترسیم گراف را که در ادامه توضیح می دهیم برآورده سازد.

.1-2 مرحله کد گذاری

2

چون در حالت کلی مکان هایی که رأس ها باید در آنجا قرار داشته باشند در این الگوریتم ثابـت اسـت، ابتـدا آرایـه ای تعریـف
کردیم به نام gr که مختصات مکان هایی را که باید گره ها در آنها قرار داشته باشد، در آن قرار دادیم (این مکان ها توسط کـاربر

مشخص می گردد)، سپس ژن را به این صورت تعریف کردیم که ( با فرض اینکه خانه اول ژن عـدد N باشـد) نشـان مـی دهـد
مختصات گره N در gr[1] قرار دارد و برای بقیه گره ها هم بدین گونه است. بنابراین هر ژن عددی را نشان مـی دهـد کـه بـه طورغیر مستقیم توسط آرایه gr موقعیت گره را نشان می دهد.

.2-2 تولید جمعیت اولیه

در این مرحله باید مقادیر کروموزوم را مقدار دهی اولیه کنیم. برای این کار به این صورت عمل می کنیم که طـول هـر کرومـوزوم برابرNumber (تعداد گره های گراف) است، بنابراین باید اعداد 1 تا Number در هر کروموزوم به صورت تصادفی قرار داشته

باشد. برای همین منظور ما الگوریتم تولید جمعیت را طوری طراحی کردیم کـه بـرای هـر کرومـوزوم جـای اعـداد را بصـورت تصادفی قرار دهد.

.3-2 تابع ارزیابی
یکی از مهمترین بخش های الگوریتم ژنتیک می باشد که برای بررسی برتری یک کرومـوزوم نسـبت بـه کرومـوزوم دیگـر بکـار میرود. و ما برای اینکه تابع ارزیابی را برای این الگوریتم مطرح کنیم ابتدا معیارهای تابع ارزیابی رابصورت خلاصه بیان می کنیم.
آ) تعداد برخورد کمتر بین یالهای گراف

بر اساس این معیار گراف باید طوری ترسیم شود که برخورد یال های گراف کمینه باشد.

ب) عدم برخورد یالهای گراف با اضلاع حفره و اضلاع چند ضلعی
با توجه به این معیار گراف را طوری رسم می کنیم که یالهای گراف اصلا ً با اضلاع حفره و اضلاع چند ضـلعی برخـورد نداشـته باشد. با توجه به اینکه در این پروژه فرض شده است چند ضـلعی محـدب اسـت برخـوردی بـین یـال هـای گـراف و اضـلاع
چندضلعی اتفاق نمی افتد اما تعداد یال های برخورد کننده با اضلاع حفره باید صفر باشد.

پ) قرارگیری گره ها درون چند ضلعی و خارج حفره.
در این حالت باید گراف را بصورتی رسم کنیم که گره ها حتما ً در داخل چند ضلعی و خارج حفره قرار گیرنـد، بـه ایـن منظـور تابعی تعریف کردیم که بررسی می کند آیا هریک از گره ها داخل چند ضلعی و خارج حفره قراردارند یا نه ؟ ولی در این مرحلـه

به این علت که جای گره ها ثابت است نیازی به بررسی این معیار نیست.

ت) فاصله بیشینه گره های گراف از یکدیگر .
در این قسمت باید الگوریتم بتواند حتی الامکان فاصله بین گرههای گراف را بیشتر کند و گراف را طوری رسم کنـد کـه تـا حـد

امکان فاصله ی بین گره ها بیشتر گردد.

3

ث) فاصله بیشینه گره ها از اضلاع چند ضلعی
با توجه به این معیار باید سعی شود گراف طوری رسم گردد که فاصله گره ها از اضلاع حفره و چند ضلعی ماکزیمم گردد

ج) فاصله ی بیشینه بین گره های گراف و یالهای گراف
این معیار بیان می کند گراف طوری باید ترسیم شود که فاصله بین یال ها و گره های گراف کاهش یابد.

چ)کمینه کردن تعداد خم ها در ترسیم یال های گراف
با توجه به اینکه هر چه تعداد خم های گراف کمتر باشد ترسیم بهتری را خواهیم داشت، این معیار تعداد کمینه یال های گراف را تعین می کند.

ح) بیشینه کردن تعداد زاویای بالا بین یال های متصل به هر یک از گره ها
معیار بعدی که برای ترسیم زیباتر در این الگوریتم استفاده شده است بیشینه کردن تعداد زاویای بالا متصل به هر گـره اسـت.برای اینکار مجموع یک یک زوایا را محاسبه کرده و در تابع ارزیابی قرار می دهیم.(شکل (1

الف ب

شکل .1 نمایش یک گراف با زوایای داخلی متفاوت

خ) بیشینه کردن فاصله میان برخورد دو یال با یکدیگر
با توجه به این معیار ما سعی می کنیم تا فاصله میان دو نقطه انتهایی در برخورد یال های گراف با یکدیگر را افـزایش دهـیم. ایـن
کار باعث می شود تا ترسیم به سمتی سوق یابد که برخورد بین یال ها از بین برود.

4

شکل.2 نمایش یک گراف و فاصله های برخورد دو یال

شکل.3 نمایش یک گراف و فاصله های برخورد دو یال

به عنوان مثال در شکل 2 اگر ( d  ABS (R1  R2 و در شکل 3 اگر ( . d1  ABS (R1  R2 واضح است کـه d1  d
. پس گراف شکل 3 بهتر از گراف شکل2 است زیرا اگر گره 4 در مراحل بعدی به سمت بالا حرکت کند، برخورد دو یال از بـین

خواهد رفت.

5

در این الگوریتم چون موقعیت اولیه گره ها ثابت و مشخص است بنابراین فقط دو معیار از معیارهای فـوق بکـار رفتـه اسـت کـه شامل معیارهای آ ( کمینه کردن تعداد برخورد یالهای گراف با یکدیگر) و ب (کمینه کردن تعـداد برخـورد یـال هـای گـراف بـا

اضلاع حفره و چندضلعی) است.

.4-2 جهش

یکی از مراحل الگوریتن ژنتیک می باشد که با تغییر یک کروموزوم که بصورت تصادفی انتخاب می شود، جـواب هـای جدیـدی
برای مساله ایجاد می کند. و ما در این الگوریتم از جهش دو نقطه ای استفاده شده است.
.5-2 بازترکیب

در این مرحله از الگوریتم ژنتیک دو کروموزوم بصورت تصادفی انتخاب شده و از یک نقطه مشخص مقدار دو کروموزوم بـا هـم جابجا شده و کروموزوم های جدید را ایجاد می کند. در این الگوریتم از بازترکیب یک نقطه ای استفاده شده است.

.6-2 روش انتخاب

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

.7-2 توقف الگوریتم
این معیار بیان می کند که الگوریتم تا چه زمانی مراحل فوق را تکرار نماید. . هرچند روش تعداد تکرار تا رسیدن به جواب قابـل قبول به نظر بهتر می رسد، به این صورت که این الگوریتم مراحل فوق (جهش، بازترکیب، تـابع ارزیـابی و انتخـاب) را تـا جـایی

تکرار می کند که به جواب قابل قبول یا همان عدم برخورد یالهای گراف با یکدیگر یا با اضلاع انجام می دهد.به عبارت دیگـر در این الگوریتم حداقل محدودیت ها باید ارضا شوند. با آنکه گراف (طبق فرض مساله ) مسطح هست ولی چون مکان قـرار گـرفتن گره ها ثابت است (و از خم در این الگوریتم استفاده نمی شود ) ممکن است هنوز در این مرحله محدودیت ها ارضا نشوند. پـس ما از روش تکرار ثابت استفاده نمودیم.
-3 ترسیم گراف مسطح در چند ضلعی حفره دار توسط الگوریتم دوم

در این الگوریتم که کامل کننده الگوریتم دوم است، موقعیت ابتدایی گره ها را مقدار کمی می لغزانیم و این کـار را در هـر تکـرار

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

حفره را درون یکی از وجه های گراف قرار می دهد. حال مراحل مختلف این الگوریتم را بصورت خلاصه بیان می کنیم.
.1-3 کد گذاری
در این الگوریتم هر ژن مختصات x و y هر گره در صفحه را در خود نگهداری می کند و هر کروموزوم شامل N ژن اسـت N)

تعداد گره های گراف است.) که موقعیت تمام گره های گراف را نگهداری می کند.
.2-3 تولید جمعیت اولیه
در این مرحله باید مقادیر کروموزوم را مقدار دهی اولیه کنیم. برای این کار از بهینه ترین کروموزوم های الگوریتم قبل استفاده

می کنیم و با جابجایی اندک (لغزش) مکان گره ها کروموزوم های جدید را تولید می کنیم.

6

.3-3 تابع ارزیابی
معیارهایی که در این الگوریتم برای بررسی زیبایی ترسیم گراف بکار گرفته شدند شامل معیارهای آ (کمینه کردن تعـداد برخـورد

یالهای گراف با یکدیگر) ، ب ( کمینه کردن تعداد برخورد یال های گراف با اضلاع حفره و چندضلعی ) ، پ (قرارگرفتن گره ها
درون چند ضلعی و خارج حفره) ، ت (کمینه کردن مجموع فاصله گره های گراف از یکدیگر) ، ث (بیشینه کردن مجموع فاصـله

گره های گراف با یکدیگر و از اضلاع چند ضلعی ) ، ج (بیشینه کردن مجموع فاصله گره های گراف از یـال هـای گـراف) ، ح
(بیشینه کردن تعداد زوایای بالا بین یال های متصل به هر یک از گـره هـا) و خ (بیشـینه کـردن فاصـله میـان برخـورد دو یـال بـا یکدیگر) است.

.4-3 جهش

در این الگوریتم از جهش یک نقطه ای استفاده شده است.
.5-3 بازترکیب
در این الگوریتم نیز از بازترکیب یک نقطه ای استفاده شده است.
.6-3 روش انتخاب
برای انتخاب کروموزوم در این روش مانند الگوریتم قبلی از روش انتخاب قطعی استفاده شده است

.7-3 توقف الگوریتم

در این الگوریتم از روش تعداد تکرار تا رسیدن به جواب قابل قبول استفاده شده است، به این صورت کـه ایـن الگـوریتم مراحـل

فوق (جهش، بازترکیب، تابع ارزیابی و انتخاب) را تا جایی تکرار می کند که به جواب قابل قبول یا همـان عـدم برخـورد یالهـای

گراف با یکدیگر یا با اضلاع انجام می دهد.به عبارت دیگر در این الگوریتم حداقل محدودیت ها باید ارضا شوند.
-4 ترسیم گراف مسطح در چند ضلعی حفره دار توسط الگوریتم جدید

ما برای حل این مساله روش دیگری را توسط الگوریتم ژنتیک جدیدی پیشنهاد کردیم که بر این ایده استوار است که گـراف را بـا

توجه به فرضیات موجود(جای گره ها مشخص و ثابت است) و بدون تغییر موقعیت گره ها طوری ترسیم کنـد کـه بـین هـیچ دو یالی برخورد صورت نگیرد، چون طبق فرض مساله گراف مسطح است.

بنابراین باید در هنگام برخورد دو یال با یکدیگر یا با اضلاع حفره یال را خم دهیم .

به عنوان مثال الگوریتم باید شکل 4 (الف) را به شکل 4 (ب) تبدیل کند.در ادامه به تشـریح راه حـل پیشـنهادی در مـورد ایـن

الگوریتم می پردازیم
.1-4 کدگذاری

7

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

آ- آرایه : cr این آرایه مختصات نقاط گره ها(اعم از مجازی و حقیقی) را در خود ذخیره می کند.

ب- آرایه : edge این آرایه گره های ابتدایی و پایانی کل یالهای گراف (هم یالهای حقیقی، هم یالهای مجازی) را در خود نگـه مـی دارد.

نکته این است که هر خانه آرایه edge از سه قسمت تشکیل شده است : -A متغییر : x گره ابتدایی یال را در خود نگهداری می کند.

-B متغییر : y گره انتهایی یال را در خود نگهداری می کند.

-C متغیر : type نوع یال(برای اینکه مشخص شود آیا این یال معتبر است یا نه) را بیان می کند.
کاربرد متغییر type به این صورت است که در ابتدا مقدار type برای تمام یال ها یک است. در هنگام انجام عملیـات هنگـامی کـه یک یال به یال دیگری (یا با اضلاع حفره) برخورد کرد type آن را صفر کرده (یال حذف می شود) و یک رأس مجـازی ایجـاد مـی
ب K 4
کنیم. سپس این یال راشکلبهدو. یالنمایشتبدیلگراف مسطحمیکنیم4 بصورتیبادوترسی مکهمتفاوتازیک گره یال اصلی به گره مجازی و از گره مجازی به گره دوم یـال
الف

اصلی اتصال بر قرار می شود(باید توجه شود که در هنگام ترسیم فقط یال هایی را رسم می کنیم که مفدار متغیر type بـرای آنهـا برابر 1 باشد.)

.2-4 تولید جمعیت اولیه
در این روش برای ایجاد جمعیت اولیه به این صورت عمل شده است که در تولید جمعیت اولیـه تعـداد گـره هـا و یـال هـای

گراف در هر کروموزوم دقیقا برابر تعداد گره ها و یال ها در گراف اصلی است.(در جمعیت اولیه گره و یال مجازی وجود ندارد.) پس در جمعیت اولیه مشخصات گره ها و یال های گراف را عینا در کروموزوم کپی می کنیم.

.3-4 تابع ارزیابی
معیارهای ارزیابی در این الگوریتم همانند معیارهای الگوریتم دوم است بعلاوه اینکه کمینه کردن تعداد خم ها را نیـز داراسـت.(در

الگوریتم های قبل به علت آنکه یال ها مستقیم و بدون خم بودند ااین معیار بررسی نشده است.)
.4-4 جهش
در این الگوریتم از جهش یک نقطه ای استفاده شده است.

.5-4 بازترکیب
در این الگوریتم نیز مانند دو الگوریتم قبلی از بازترکیب یک نقطه ای استفاده شده است.
.6-4 روش انتخاب کروموزوم جدید

برای انتخاب کروموزوم جدید در اینجا از روش Rank Power استفاده شده است.