נושא הפרוייקט

מספר פרוייקט מחלקה שמות סטודנטים אימייל שמות מנחים

פתירת בעיית הקליקה המקסימלית באמצעות אלגוריתמים בהשראת עולם הטבע

Exploring Natural-Inspired Algorithms for Solving the Max Clique Problem

תקציר בעיברית

רקע כללי
בחברת רפאל עלה הצורך לבחון מספר דרכים שונות לפתרון בעיה אלגורתימית איתה הצוות של אורי ונעם מתמודד במהלך פיתוח מערכת מבצעית.
לשם כך הבעיה עברה בלמו"ס, לבעיית "הרכבת צוות העבודה".

תיאור הבעיה
בחברה מסוימת ישנם קבוצות עובדים בעלי הכשרה מקצועית שונה - מנהלי פרויקט, מהנדסי מכונות, מתכנתים, ועוד.
עבור פרוייקט מיוחד, החברה נדרשת להקים צוות שיכיל עובד אחד בלבד מכל קבוצה מקצועית שקיימת. 
מכיוון שמדובר בפרויקט עם שעות עבודה קשות ועבודה במקום צפוף, הוגדר שכל העובדים בצוות החדש חייבים להיות חברים אחד של השני. 
לאחר תשאול של כלל העובדים בחברה לגבי חבריהם קיבלנו מטריצת חברות בין העובדים, שמסמנת האם זוג עובדים חברים או לא.
צריך להרכיב צוות לפרויקט החדש, כך שכל העובדים בצוות חברים אחד של השני והצוות גדול ככל שניתן, כלומר מכמה קבוצות מקצועיות שונות שאפשר.

תיאור פורמלי
בהינתן גרף לא ממשוקלל ולא מכוון הבנוי מקבוצות בלתי תלויות של קדקודים (המיוצג ע"י מטריצת הקשתות ביניהן), נרצה למצוא את הקליקה המקסימלית בגרף.
קלט: מטריצת קשתות, מערך המכיל את קבוצות הקדקודים הבלתי תלויים.
פלט: קליקה של קדקודים בגרף, גדולה ככל שניתן.

דרכי הפתרון
בפרויקט פתרנו את הבעיה האלגוריתמית באמצעות מספר אלגוריתמים שמבוססים על עולם הטבע:

1. אלגוריתמים אבולוציונים:
אלגוריתמי חיפוש המבוססים על עקרונות הגנטיקה והברירה הטבעית.
האלגוריתם מחקה את תהליך האבולוציה כדי ליצור פתרונות טובים יותר באופן איטרטיבי.
התהליך כולל פעולות של יצירת אוכלוסיה ראשונית, הערכה, בחירה, ויישום של אופרטורים גנטיים כגון שחלוף ומוטציה.

2. אלגוריתם מושבת קן הנמלים:
  אלגוריתם מטאוריסטי שנבנה בהשראת התנהגותן של הנמלים.
בטבע, הנמלים מתקשרות באמצעות הפרשת פרומונים שבין היתר מאותתים על מציאת מקור מזון.
האלגוריתם שולח מספר רב של נמלים למצוא קליקות מקסימליות בגרף ומתחזק מטריצת פרומונים שממקדת את הסוכנים באיזורי חיפוש שזוהו כאטרקטיביים.

תקציר באנגלית

Background
At Rafael there is a need to examine several different ways to solve an algorithmic problem that Ori and Noam's team faces during the development of an operational system.
Due to information classification issues, the original problem was converted to the problem of "assembling the work team".

Problem Description
In a certain company there are groups of employees with different professional training - project managers, mechanical engineers, programmers, etc.
For a special project, the company is required to establish a team that will contain only one employee from each existing professional group.
But since it is a project with hard working hours and working in a crowded place, it was defined that all the employees in the new team must be friends of each other.
After questioning all the employees in the company about their friends, we received a friendship matrix between the employees, which indicates whether a pair of employees are friends or not.
Build a team for the new project, so that all the employees in the team are friends of each other and the team is as large as possible, that is, from as many different professional groups as possible.

Formal Description
Given an unweighted and undirected graph built from independent sets of vertices (represented by the membership matrix between them), we would like to find the maximal clique in the graph.

Input: the membership matrix between the employees, the database of employees arranged by type of employee
Output: a clique of vertices in the graph, as large as possible.


Solution Methodology
In the project we solved the algorithmic problem using several algorithms based on the natural world:
1. GA - Genetic Algorithms:
Search algorithms based on the principles of genetics and natural selection.
The algorithm mimics the evolution process to iteratively generate better solutions.
The process includes actions of creating an initial population, evaluation, selection, and application of genetic operators such as crossover and mutation.

2. ACO - Ant Colony Optimization:
A metaheuristic algorithm built inspired by the behavior of ants.
In nature, ants communicate by secreting pheromones that, among other things, signal finding a food source.
The algorithm sends a large number of ants to find maximal cliques in the graph and maintains a pheromone matrix that focuses the agents on search areas identified as attractive.