الگوریتم کلونی مورچگان یا Ant Colony Optimization که به‌اختصار ACO نامیده می‌شود، یکی از الگوریتم‌های هوش ازدحامی برای حل مسائل بهینه‌سازی ترکیبی است.

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

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

در الگوریتم ACO نیز مجموعه‌ای از عامل‌های مصنوعی یا «مورچه‌ها» جواب‌های احتمالی را می‌سازند. جواب‌های بهتر فرومون بیشتری دریافت می‌کنند و احتمال استفاده از اجزای آنها در تکرارهای بعدی افزایش پیدا می‌کند.

الگوریتم کلونی مورچگان به‌خصوص برای مسائل زیر مناسب است:

• مسئله فروشنده دوره‌گرد
• مسیریابی وسایل نقلیه
• زمان‌بندی
• تخصیص وظایف
• طراحی شبکه
• مسیریابی بسته‌های شبکه
• انتخاب مسیر در گردش‌کار
• ترکیب سرویس‌ها
• برنامه‌ریزی زنجیره تأمین
• بهینه‌سازی مسیر عامل‌های هوش مصنوعی

الگوریتم کلونی مورچگان چیست؟

ACO یک چارچوب فراابتکاری و احتمالاتی برای پیدا کردن جواب‌های مناسب در مسائل بهینه‌سازی است.

در این الگوریتم، هر مورچه یک جواب را مرحله‌به‌مرحله می‌سازد. انتخاب هر مرحله معمولاً به دو عامل وابسته است:

1. مقدار فرومون موجود روی آن انتخاب
2. جذابیت ابتکاری یا Heuristic آن انتخاب

پس از ساخته‌شدن جواب‌ها:

• کیفیت هر جواب محاسبه می‌شود.
• بخشی از فرومون‌های قبلی تبخیر می‌شوند.
• مسیرهای استفاده‌شده در جواب‌های بهتر فرومون بیشتری دریافت می‌کنند.
• نسل بعدی مورچه‌ها با استفاده از اطلاعات جدید حرکت می‌کند.

نخستین الگوریتم‌های ACO در اوایل دهه ۱۹۹۰ توسط Marco Dorigo و همکارانش معرفی شدند. چارچوب عمومی Ant Colony Optimization بعداً برای قرار دادن الگوریتم‌های مختلف این خانواده در یک ساختار مشترک توسعه یافت.

الگوریتم ACO چگونه از مورچه‌های واقعی الهام گرفته است؟

فرض کنید دو مسیر میان لانه مورچه‌ها و غذا وجود دارد:

• مسیر اول کوتاه است.
• مسیر دوم طولانی است.

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

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

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

در ACO، این دو سازوکار در کنار هم قرار می‌گیرند:

• تقویت مسیرهای موفق
• فراموش‌کردن تدریجی مسیرهای قدیمی

مفاهیم اصلی الگوریتم کلونی مورچگان

مورچه مصنوعی

هر مورچه مصنوعی یک عامل جست‌وجو است که یک جواب کامل یا بخشی از یک جواب را می‌سازد.

برای مثال، در مسئله فروشنده دوره‌گرد، هر مورچه ترتیبی از شهرها ایجاد می‌کند:

تهران ← کرج ← قزوین ← رشت ← تهران

فرومون

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

مقدار فرومون روی مسیر میان دو گره i و j معمولاً با نماد زیر نمایش داده می‌شود:

τij\tau_{ij}

هرچه τ بیشتر باشد، احتمال انتخاب آن مسیر افزایش پیدا می‌کند.

اطلاعات ابتکاری

اطلاعات ابتکاری یا Heuristic Information دانشی است که مستقیماً از مسئله به دست می‌آید.

در مسئله کوتاه‌ترین مسیر، معکوس فاصله می‌تواند معیار مناسبی باشد:

ηij=1dij\eta_{ij}=\frac{1}{d_{ij}}

در این رابطه:

• d فاصله میان دو شهر است.
• η جذابیت ابتکاری مسیر است.

مسیر کوتاه‌تر مقدار η بیشتری خواهد داشت.

تبخیر فرومون

در هر تکرار بخشی از فرومون تبخیر می‌شود:

τij←(1−ρ)τij\tau_{ij} \leftarrow (1-\rho)\tau_{ij}

در این رابطه، ρ نرخ تبخیر است.

تبخیر چند هدف دارد:

• کاهش اثر تصمیم‌های قدیمی
• جلوگیری از افزایش نامحدود فرومون
• حفظ توانایی اکتشاف مسیرهای جدید
• کاهش احتمال همگرایی زودرس

تقویت فرومون

پس از ارزیابی جواب‌ها، مورچه‌ها روی مسیرهای استفاده‌شده فرومون اضافه می‌کنند.

یک فرمول ساده:

Δτijk={QLkاگر مورچه k از مسیر i,j استفاده کرده باشد0در غیر این صورت\Delta\tau_{ij}^{k}= \begin{cases} \frac{Q}{L_k} & \text{اگر مورچه } k \text{ از مسیر } i,j \text{ استفاده کرده باشد}\\ 0 & \text{در غیر این صورت} \end{cases}

در این رابطه:

• Q یک ثابت مقیاس است.
• Lₖ طول مسیر مورچه k است.

از آنجا که مسیر کوتاه‌تر L کمتری دارد، فرومون بیشتری دریافت می‌کند.

فرمول انتخاب مسیر در ACO

احتمال حرکت مورچه k از گره i به گره j معمولاً چنین محاسبه می‌شود:

Pijk=τijαηijβ∑l∈NikτilαηilβP_{ij}^{k}= \frac{ \tau_{ij}^{\alpha} \eta_{ij}^{\beta} }{ \sum_{l\in N_i^k} \tau_{il}^{\alpha} \eta_{il}^{\beta} }

اجزای فرمول:

اگر α زیاد باشد، مورچه‌ها بیشتر از تجربه جمعی پیروی می‌کنند. اگر β زیاد باشد، انتخاب‌ها بیشتر تحت‌تأثیر اطلاعات محلی مانند فاصله قرار می‌گیرند.

نقش پارامترهای اصلی ACO

پارامتر Alpha

پارامتر α میزان اثر فرومون را کنترل می‌کند.

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

اگر α صفر باشد، فرومون در انتخاب مسیر اثری نخواهد داشت.

پارامتر Beta

پارامتر β اهمیت اطلاعات ابتکاری را تعیین می‌کند.

در مسئله فروشنده دوره‌گرد، مقدار بزرگ‌تر β باعث می‌شود مورچه‌ها تمایل بیشتری به انتخاب شهرهای نزدیک داشته باشند.

اگر β بیش‌ازحد بزرگ باشد، الگوریتم می‌تواند به یک روش حریصانه نزدیک شود و اثر یادگیری جمعی کاهش پیدا کند.

نرخ تبخیر Rho

پارامتر ρ میزان فراموش‌شدن فرومون‌های قبلی را تعیین می‌کند.

• تبخیر کم: حافظه طولانی‌تر، اکتشاف کمتر
• تبخیر زیاد: فراموشی سریع‌تر، اکتشاف بیشتر

ثابت Q

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

تعداد مورچه‌ها

مورچه‌های بیشتر می‌توانند تنوع جواب‌ها را افزایش دهند، اما تعداد ارزیابی‌های تابع هدف نیز بیشتر می‌شود.

مراحل اجرای الگوریتم کلونی مورچگان

فرایند ساده ACO به این صورت است:

1. مقدار اولیه فرومون مسیرها تعیین می‌شود.
2. هر مورچه از یک نقطه شروع حرکت می‌کند.
3. مورچه بر اساس فرومون و اطلاعات ابتکاری گزینه بعدی را انتخاب می‌کند.
4. انتخاب‌ها تا ساخته‌شدن یک جواب کامل ادامه پیدا می‌کنند.
5. کیفیت تمام جواب‌ها محاسبه می‌شود.
6. فرومون‌های قبلی تبخیر می‌شوند.
7. جواب‌های مناسب‌تر فرومون بیشتری روی اجزای خود باقی می‌گذارند.
8. بهترین جواب ذخیره می‌شود.
9. فرایند تا رسیدن به شرط توقف تکرار می‌شود.

شبه‌کد:

مقداردهی اولیه فرومون‌ها

تا زمانی که شرط توقف برقرار نشده است:
    برای هر مورچه:
        ساخت تدریجی یک جواب
        ارزیابی کیفیت جواب

    تبخیر فرومون‌های قبلی

    برای هر مورچه:
        افزایش فرومون مسیرهای استفاده‌شده
        متناسب با کیفیت جواب

    ذخیره بهترین جواب

برگرداندن بهترین جواب

مسئله فروشنده دوره‌گرد چیست؟

مسئله فروشنده دوره‌گرد یا Travelling Salesman Problem که به‌اختصار TSP نامیده می‌شود، یکی از مسائل مشهور بهینه‌سازی ترکیبی است.

در این مسئله فروشنده باید:

• از یک شهر شروع کند.
• از تمام شهرها دقیقاً یک بار بازدید کند.
• به شهر شروع بازگردد.
• مجموع مسافت طی‌شده را به حداقل برساند.

اگر تعداد شهرها n باشد، تعداد مسیرهای احتمالی با سرعت بسیار زیادی افزایش پیدا می‌کند. بررسی همه مسیرها برای تعداد زیاد شهرها عملی نیست.

الگوریتم ACO می‌تواند بدون بررسی کامل همه ترکیب‌ها، مسیر مناسبی پیدا کند. نتیجه لزوماً بهترین مسیر ریاضی نیست، اما ممکن است با هزینه محاسباتی قابل‌قبول به جواب باکیفیتی برسد.

پیاده‌سازی الگوریتم کلونی مورچگان با پایتون

در این مثال ACO را از ابتدا با NumPy پیاده‌سازی می‌کنیم و مسئله فروشنده دوره‌گرد را حل می‌کنیم.

نصب کتابخانه‌ها

pip install numpy matplotlib

تعریف شهرها

برای سادگی، هر شهر را با مختصات دوبعدی نمایش می‌دهیم:

import numpy as np


CITIES = np.array(
    [
        [0.0, 0.0],
        [2.0, 6.0],
        [3.0, 1.0],
        [5.0, 5.0],
        [8.0, 2.0],
        [7.0, 7.0],
        [1.0, 8.0],
        [9.0, 6.0],
    ],
    dtype=float,
)

محاسبه ماتریس فاصله

def build_distance_matrix(points):
    differences = (
        points[:, np.newaxis, :]
        - points[np.newaxis, :, :]
    )

    distances = np.sqrt(
        np.sum(differences ** 2, axis=2)
    )

    np.fill_diagonal(distances, np.inf)

    return distances


DISTANCES = build_distance_matrix(CITIES)

درایه DISTANCES[i, j] فاصله میان شهر i و شهر j را نشان می‌دهد.

فاصله هر شهر تا خودش برابر بی‌نهایت قرار داده شده است تا مورچه دوباره همان شهر را انتخاب نکند.

کلاس الگوریتم ACO

class AntColonyOptimizer:
    def __init__(
        self,
        distances,
        ants=30,
        iterations=150,
        alpha=1.0,
        beta=3.0,
        evaporation=0.4,
        deposit_strength=100.0,
        elite_weight=2.0,
        seed=42,
    ):
        self.distances = distances
        self.city_count = distances.shape[0]

        self.ants = ants
        self.iterations = iterations
        self.alpha = alpha
        self.beta = beta
        self.evaporation = evaporation
        self.deposit_strength = deposit_strength
        self.elite_weight = elite_weight

        self.rng = np.random.default_rng(seed)

        self.pheromone = np.ones_like(
            distances,
            dtype=float,
        )

        np.fill_diagonal(self.pheromone, 0.0)

        self.heuristic = np.zeros_like(
            distances,
            dtype=float,
        )

        valid = np.isfinite(distances)

        self.heuristic[valid] = (
            1.0 / distances[valid]
        )

    def route_length(self, route):
        total = 0.0

        for index in range(len(route)):
            current_city = route[index]
            next_city = route[
                (index + 1) % len(route)
            ]

            total += self.distances[
                current_city,
                next_city,
            ]

        return float(total)

    def choose_next_city(self, current, unvisited):
        candidates = np.array(
            list(unvisited),
            dtype=int,
        )

        pheromone_score = (
            self.pheromone[current, candidates]
            ** self.alpha
        )

        heuristic_score = (
            self.heuristic[current, candidates]
            ** self.beta
        )

        weights = pheromone_score * heuristic_score
        total = weights.sum()

        if (
            total <= 0
            or not np.isfinite(total)
        ):
            return int(self.rng.choice(candidates))

        probabilities = weights / total

        return int(
            self.rng.choice(
                candidates,
                p=probabilities,
            )
        )

    def build_route(self):
        start = int(
            self.rng.integers(self.city_count)
        )

        route = [start]
        unvisited = set(range(self.city_count))
        unvisited.remove(start)

        while unvisited:
            next_city = self.choose_next_city(
                route[-1],
                unvisited,
            )

            route.append(next_city)
            unvisited.remove(next_city)

        return route

    def evaporate(self):
        self.pheromone *= (
            1.0 - self.evaporation
        )

        np.fill_diagonal(self.pheromone, 0.0)

    def deposit(self, routes):
        for route, length in routes:
            amount = (
                self.deposit_strength / length
            )

            for index in range(len(route)):
                city_a = route[index]
                city_b = route[
                    (index + 1) % len(route)
                ]

                self.pheromone[city_a, city_b] += amount
                self.pheromone[city_b, city_a] += amount

    def deposit_elite(self, route, length):
        amount = (
            self.elite_weight
            * self.deposit_strength
            / length
        )

        for index in range(len(route)):
            city_a = route[index]
            city_b = route[
                (index + 1) % len(route)
            ]

            self.pheromone[city_a, city_b] += amount
            self.pheromone[city_b, city_a] += amount

    def run(self):
        best_route = None
        best_length = float("inf")
        history = []

        for _ in range(self.iterations):
            routes = []

            for _ in range(self.ants):
                route = self.build_route()
                length = self.route_length(route)

                routes.append((route, length))

                if length < best_length:
                    best_route = route.copy()
                    best_length = length

            self.evaporate()
            self.deposit(routes)

            self.deposit_elite(
                best_route,
                best_length,
            )

            history.append(best_length)

        return {
            "best_route": best_route,
            "best_length": best_length,
            "history": history,
        }

اجرای الگوریتم

optimizer = AntColonyOptimizer(
    distances=DISTANCES,
    ants=40,
    iterations=200,
    alpha=1.0,
    beta=3.0,
    evaporation=0.4,
    deposit_strength=100.0,
    elite_weight=2.0,
    seed=42,
)

result = optimizer.run()

print("Best route:", result["best_route"])
print("Best length:", result["best_length"])

نتیجه دقیق می‌تواند با تغییر Seed یا پارامترهای الگوریتم متفاوت باشد.

ACO یک الگوریتم تصادفی است؛ بنابراین بهتر است آن را چند بار اجرا و کیفیت نتایج را مقایسه کنید.

رسم بهترین مسیر

import matplotlib.pyplot as plt


route = result["best_route"]
closed_route = route + [route[0]]

ordered_points = CITIES[closed_route]

plt.figure(figsize=(8, 6))

plt.plot(
    ordered_points[:, 0],
    ordered_points[:, 1],
    marker="o",
)

for index, point in enumerate(CITIES):
    plt.text(
        point[0] + 0.1,
        point[1] + 0.1,
        str(index),
    )

plt.title(
    f"Best route length: "
    f"{result['best_length']:.2f}"
)

plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.show()

رسم نمودار همگرایی

plt.figure(figsize=(8, 4))

plt.plot(result["history"])

plt.xlabel("Iteration")
plt.ylabel("Best Route Length")
plt.title("ACO Convergence")
plt.grid(True)
plt.show()

اگر بهترین طول مسیر خیلی زود ثابت شود، ممکن است الگوریتم دچار همگرایی زودرس شده باشد.

پیاده‌سازی ACO با Scikit-opt

کتابخانه Scikit-opt مجموعه‌ای از الگوریتم‌های فراابتکاری مانند الگوریتم ژنتیک، PSO، تبرید شبیه‌سازی‌شده، کلونی مورچگان و Differential Evolution را ارائه می‌کند.

نصب:

pip install scikit-opt numpy

نمونه حل TSP:

import numpy as np

from sko.ACA import ACA_TSP


city_points = np.array(
    [
        [0.0, 0.0],
        [2.0, 6.0],
        [3.0, 1.0],
        [5.0, 5.0],
        [8.0, 2.0],
        [7.0, 7.0],
        [1.0, 8.0],
        [9.0, 6.0],
    ]
)


def build_distance_matrix(points):
    differences = (
        points[:, None, :]
        - points[None, :, :]
    )

    return np.sqrt(
        np.sum(differences ** 2, axis=2)
    )


distance_matrix = build_distance_matrix(
    city_points
)


def route_distance(route):
    number_of_cities = len(route)

    return sum(
        distance_matrix[
            route[index],
            route[
                (index + 1) % number_of_cities
            ],
        ]
        for index in range(number_of_cities)
    )


aco = ACA_TSP(
    func=route_distance,
    n_dim=len(city_points),
    size_pop=40,
    max_iter=200,
    distance_matrix=distance_matrix,
)

best_route, best_distance = aco.run()

print("Best route:", best_route)
print("Best distance:", best_distance)

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

مقایسه جواب با NetworkX

NetworkX یک کتابخانه پایتون برای ساخت، تحلیل و پردازش گراف‌ها و شبکه‌های پیچیده است.

این کتابخانه الگوریتم‌های تقریبی برای TSP نیز ارائه می‌کند. برای نمونه، الگوریتم Christofides در یک گراف کامل، وزن‌دار و بدون جهت یک تقریب 3/2 برای TSP متریک محاسبه می‌کند.

بنابراین در یک پروژه واقعی بهتر است نتیجه ACO را با روش‌های موجود در NetworkX یا سایر الگوریتم‌های پایه مقایسه کنید. ACO نباید بدون خط مبنای معتبر انتخاب شود.

انواع الگوریتم کلونی مورچگان

Ant System

Ant System یکی از اولین نسخه‌های الگوریتم کلونی مورچگان است. در این نسخه تمام مورچه‌ها پس از ساخت جواب می‌توانند فرومون مسیرهای خود را افزایش دهند.

Ant Colony System

Ant Colony System یا ACS تغییراتی برای افزایش تعادل میان اکتشاف و بهره‌برداری ارائه می‌کند.

در ACS معمولاً:

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

Max-Min Ant System

در Max-Min Ant System مقدار فرومون به یک بازه محدود می‌شود:

τmin⁡≤τij≤τmax⁡\tau_{\min} \leq \tau_{ij} \leq \tau_{\max}

این محدودیت مانع می‌شود یک مسیر بیش‌ازحد قوی یا مسیرهای دیگر کاملاً غیرقابل‌انتخاب شوند.

Elitist Ant System

در نسخه Elitist، بهترین جواب فرومون اضافه دریافت می‌کند. در پیاده‌سازی آموزشی این مقاله نیز elite_weight برای تقویت بهترین مسیر استفاده شد.

Rank-Based Ant System

در این روش مورچه‌ها بر اساس کیفیت جواب رتبه‌بندی می‌شوند و مقدار فرومون آنها به رتبه وابسته است.

کاربرد الگوریتم مورچگان در مسیریابی

ACO یکی از شناخته‌شده‌ترین روش‌ها برای مسائل مسیریابی است.

کاربردهای احتمالی:

• مسیر تحویل سفارش
• مسیریابی ناوگان حمل‌ونقل
• انتخاب مسیر در شبکه مخابراتی
• مسیریابی ربات
• برنامه‌ریزی بازدید نمایندگان فروش
• مسیر جمع‌آوری کالا
• مسیریابی میان مراکز توزیع
• انتخاب زنجیره سرویس‌ها

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

کاربرد ACO در زمان‌بندی

در مسائل زمان‌بندی، هر مورچه می‌تواند ترتیب اجرای وظایف یا تخصیص آنها به منابع را بسازد.

مثال‌ها:

• زمان‌بندی خطوط تولید
• تخصیص کار به ماشین‌ها
• برنامه‌ریزی شیفت کارکنان
• زمان‌بندی پردازش‌های ابری
• ترتیب اجرای درخواست‌ها
• برنامه‌ریزی وظایف عامل‌های هوش مصنوعی

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

Objective =
CompletionTime
+ DelayPenalty
+ ResourceCost
+ ConstraintPenalty

کاربرد ACO در انتخاب ویژگی

در مسائل یادگیری ماشین می‌توان از نسخه‌های دودویی ACO برای انتخاب ویژگی‌ها استفاده کرد.

هر ویژگی یک تصمیم است:

1 = ویژگی انتخاب شود
0 = ویژگی حذف شود

تابع هدف می‌تواند خطای مدل و تعداد ویژگی‌ها را هم‌زمان در نظر بگیرد:

Objective=ValidationError+λSelectedFeaturesAllFeaturesObjective = ValidationError + \lambda \frac{SelectedFeatures}{AllFeatures}

به این ترتیب الگوریتم به‌دنبال مدلی است که علاوه بر کیفیت مناسب، ویژگی‌های کمتری داشته باشد.

کاربرد ACO در طراحی گردش‌کار هوش مصنوعی

یک برنامه هوش مصنوعی سازمانی ممکن است برای پاسخ به هر درخواست چند مسیر داشته باشد:

دریافت درخواست
    ↓
طبقه‌بندی
    ↓
پاسخ مستقیم یا بازیابی اطلاعات
    ↓
مدل سریع یا مدل دقیق
    ↓
اعتبارسنجی
    ↓
پاسخ یا ارجاع انسانی

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

در چنین مسئله‌ای:

• هر گره یک مرحله پردازش است.
• هر یال یک انتخاب ممکن است.
• فرومون میزان موفقیت تاریخی مسیر را نشان می‌دهد.
• اطلاعات ابتکاری می‌تواند بر اساس هزینه یا تأخیر محاسبه شود.
• تابع هدف کیفیت، هزینه و زمان را ترکیب می‌کند.

بااین‌حال، ACO نباید مستقیماً و بدون محدودیت، کنترل اقدامات حساس را در اختیار بگیرد. قوانین قطعی، مجوزها و محدودیت‌های عملیاتی باید در سمت سرور اجرا شوند.

استفاده از ACO برای مسیریابی میان مدل‌های هوش مصنوعی

فرض کنید برنامه شما به چند مدل دسترسی دارد:

• مدل سریع و اقتصادی
• مدل متعادل
• مدل دقیق و گران‌تر

برای هر نوع درخواست، چند مسیر احتمالی وجود دارد:

مدل سریع
مدل دقیق
مدل سریع ← ارزیابی ← مدل دقیق
بازیابی اطلاعات ← مدل سریع
بازیابی اطلاعات ← مدل دقیق ← اعتبارسنجی

هر مسیر می‌تواند بر اساس معیارهای زیر ارزیابی شود:

• کیفیت پاسخ
• زمان پاسخ
• هزینه
• نرخ خطا
• تعداد فراخوانی مدل
• نرخ نیاز به Fallback
• رضایت کاربر

یک تابع هزینه نمونه:

RouteCost=w1(1−Quality)+w2Cost+w3Latency+w4ErrorRateRouteCost = w_1(1-Quality) +w_2 Cost +w_3 Latency +w_4 ErrorRate

ACO می‌تواند مسیرهایی را که در داده‌های ارزیابی نتیجه بهتری دارند تقویت کند.

این روش برای طراحی آزمایش یا پیشنهاد سیاست مسیریابی مفید است، اما در محیط عملیاتی باید محدودیت‌هایی مانند سقف هزینه، مدل‌های مجاز، زمان انتظار و شرایط Fallback نیز به‌صورت قطعی کنترل شوند.

اتصال ارزیابی مسیرها به API درواره

API درواره با ساختار OpenAI سازگار است و می‌توان مدل‌های مختلف را از طریق یک Client مشترک ارزیابی کرد.

ابتدا کتابخانه OpenAI را نصب کنید:

pip install openai

متغیرهای محیطی:

export DARVAREH_API_KEY="YOUR_API_KEY"
export DARVAREH_FAST_MODEL="YOUR_FAST_MODEL_ID"
export DARVAREH_QUALITY_MODEL="YOUR_QUALITY_MODEL_ID"

ساخت Client:

import os
import time

from openai import OpenAI


client = OpenAI(
    api_key=os.environ["DARVAREH_API_KEY"],
    base_url="https://api.darvareh.ir/v1",
)

FAST_MODEL = os.environ["DARVAREH_FAST_MODEL"]
QUALITY_MODEL = os.environ["DARVAREH_QUALITY_MODEL"]

فراخوانی مدل و اندازه‌گیری زمان

def call_model(model, messages):
    started_at = time.perf_counter()

    response = client.chat.completions.create(
        model=model,
        temperature=0.2,
        max_tokens=500,
        messages=messages,
    )

    latency = time.perf_counter() - started_at

    answer = (
        response.choices[0].message.content
        or ""
    )

    usage = response.usage

    total_tokens = (
        usage.total_tokens
        if usage is not None
        else 0
    )

    return {
        "answer": answer,
        "latency": latency,
        "tokens": total_tokens,
    }

تعریف مسیرهای ممکن

ROUTES = {
    "fast_only": [
        FAST_MODEL,
    ],
    "quality_only": [
        QUALITY_MODEL,
    ],
    "fast_then_quality": [
        FAST_MODEL,
        QUALITY_MODEL,
    ],
}

اجرای یک مسیر

def execute_route(route_name, question):
    messages = [
        {
            "role": "system",
            "content": (
                "پاسخی دقیق، کوتاه و فارسی ارائه کن. "
                "از تولید اطلاعات حدسی خودداری کن."
            ),
        },
        {
            "role": "user",
            "content": question,
        },
    ]

    results = []

    for model in ROUTES[route_name]:
        result = call_model(model, messages)
        results.append(result)

        messages.append(
            {
                "role": "assistant",
                "content": result["answer"],
            }
        )

        messages.append(
            {
                "role": "user",
                "content": (
                    "پاسخ قبلی را بررسی و در صورت نیاز "
                    "اصلاح کن. فقط پاسخ نهایی را بنویس."
                ),
            }
        )

    return {
        "answer": results[-1]["answer"],
        "latency": sum(
            item["latency"]
            for item in results
        ),
        "tokens": sum(
            item["tokens"]
            for item in results
        ),
        "calls": len(results),
    }

این کد فقط روش اندازه‌گیری یک مسیر را نشان می‌دهد. برای استفاده در ACO باید هر مسیر به‌صورت مجموعه‌ای از گره‌ها نمایش داده و کیفیت آن روی یک مجموعه ارزیابی ثابت محاسبه شود.

طراحی تابع هدف برای مسیرهای مدل

فرض کنید برای هر مسیر این مقادیر را داریم:

• quality: امتیاز بین صفر و یک
• latency: زمان پاسخ بر حسب ثانیه
• cost: هزینه محاسبه‌شده
• error_rate: نرخ خطا

تابع هدف:

def route_objective(
    quality,
    latency,
    cost,
    error_rate,
):
    return (
        0.55 * (1.0 - quality)
        + 0.15 * normalized_latency(latency)
        + 0.20 * normalized_cost(cost)
        + 0.10 * error_rate
    )

وزن‌ها باید بر اساس نیاز محصول تعیین شوند. در یک دستیار تعاملی ممکن است تأخیر اهمیت بیشتری داشته باشد، اما در پردازش دسته‌ای کیفیت یا هزینه اولویت بالاتری دارد.

فرومون در مسیریابی مدل چه معنایی دارد؟

در یک نمونه آزمایشی، مقدار فرومون هر یال می‌تواند نشان دهد آن انتقال در مسیرهای موفق چند بار استفاده شده است.

مثلاً:

طبقه‌بندی → مدل سریع
بازیابی → مدل دقیق
مدل سریع → اعتبارسنج
اعتبارسنج → Fallback

اگر مسیر زیر کیفیت مناسبی با هزینه پایین داشته باشد:

طبقه‌بندی
→ بازیابی
→ مدل سریع
→ اعتبارسنجی
→ پاسخ

فرومون یال‌های آن افزایش پیدا می‌کند و مورچه‌های بعدی احتمال بیشتری دارد مسیر مشابهی بسازند.

برای آشنایی با معماری چندمدلی، مقاله معماری چندمدلی و چندارائه‌دهنده هوش مصنوعی را مطالعه کنید.

کنترل هزینه ACO متصل به API

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

تعداد تقریبی فراخوانی‌ها:

تعداد فراخوانی‌ها =
تعداد مورچه‌ها
× تعداد تکرارها
× تعداد نمونه‌های ارزیابی
× میانگین مراحل هر مسیر

مثال:

۱۰ مورچه
× ۸ تکرار
× ۲۰ پرسش
× ۲ فراخوانی
= ۳۲۰۰ درخواست

برای کاهش هزینه:

• با تعداد کمی مورچه و تکرار شروع کنید.
• نتیجه مسیرهای تکراری را Cache کنید.
• آزمایش اولیه را روی مجموعه کوچک انجام دهید.
• فقط جواب‌های برتر را روی مجموعه کامل اجرا کنید.
• برای غربالگری اولیه از مدل اقتصادی‌تر استفاده کنید.
• بودجه و تعداد ارزیابی را محدود کنید.
• مسیرهای نامعتبر را قبل از فراخوانی API حذف کنید.
• ارزیابی‌های مستقل را به‌صورت Batch یا موازی اجرا کنید.

چگونه کیفیت مسیر را ارزیابی کنیم؟

ارزیابی مسیر فقط با طول پاسخ یا چند کلمه کلیدی کافی نیست.

ترکیبی از معیارهای زیر مناسب‌تر است:

• صحت پاسخ
• کامل‌بودن پاسخ
• رعایت دستور
• معتبر بودن JSON
• کیفیت استناد
• نرخ پاسخ بدون مدرک
• نرخ موفقیت ابزارها
• هزینه
• زمان پاسخ
• نرخ Timeout
• ارزیابی انسانی
• امتیاز مدل داور
• نرخ حل موفق مسئله کاربر

برای طراحی مجموعه آزمون، مقاله ارزیابی مدل‌های هوش مصنوعی و Evals را مطالعه کنید.

مدیریت محدودیت‌ها در ACO

مسائل واقعی معمولاً محدودیت‌هایی دارند.

برای مثال:

• هر شهر باید دقیقاً یک بار بازدید شود.
• مسیر باید از نقطه مشخصی شروع شود.
• ظرفیت خودرو نباید نقض شود.
• هزینه مسیر نباید از بودجه بیشتر شود.
• بعضی مراحل گردش‌کار اجباری هستند.
• پس از عملیات حساس باید اعتبارسنجی انجام شود.
• فقط مدل‌های مشخصی برای یک نوع داده مجاز هستند.

روش‌های مدیریت محدودیت:

محدودکردن گزینه‌های قابل انتخاب

در هر مرحله فقط گزینه‌های معتبر در مجموعه انتخاب قرار می‌گیرند.

این روش معمولاً بهتر از ساخت جواب نامعتبر و جریمه‌کردن آن است.

تابع جریمه

اگر جواب محدودیتی را نقض کند، مقدار جریمه به تابع هدف اضافه می‌شود:

Objectivefinal=Objective+λPenaltyObjective_{final} = Objective + \lambda Penalty

اصلاح جواب

بعد از ساخته‌شدن مسیر، بخش‌های نامعتبر آن اصلاح می‌شوند.

نمایش تضمین‌کننده

ساختار جواب به شکلی طراحی می‌شود که تولید بعضی مسیرهای نامعتبر از ابتدا امکان‌پذیر نباشد.

همگرایی زودرس در ACO

همگرایی زودرس زمانی رخ می‌دهد که یک یا چند مسیر خیلی زود مقدار فرومون زیادی دریافت کنند و مورچه‌ها تقریباً همیشه همان مسیرها را انتخاب کنند.

نشانه‌ها:

• شباهت زیاد جواب‌های مورچه‌ها
• ثابت‌ماندن بهترین جواب
• نزدیک‌شدن احتمال بعضی مسیرها به صفر
• نتایج بسیار متفاوت با تغییر Seed
• کاهش سریع تنوع مسیرها

راهکارها:

• افزایش نرخ تبخیر
• محدودکردن حداقل و حداکثر فرومون
• افزایش تعداد مورچه‌ها
• تقویت فقط بهترین جواب‌های معتبر
• مقداردهی مجدد فرومون پس از رکود
• استفاده از جست‌وجوی محلی
• افزایش تصادفی‌بودن انتخاب‌ها
• کاهش مقدار α
• اجرای چندباره با Seedهای مختلف

ترکیب ACO با جست‌وجوی محلی

ACO معمولاً می‌تواند با یک روش Local Search ترکیب شود.

در مسئله TSP، پس از ساخت مسیر توسط مورچه می‌توان از روش 2-opt استفاده کرد:

1. دو یال از مسیر انتخاب می‌شوند.
2. بخشی از ترتیب مسیر معکوس می‌شود.
3. اگر مسیر جدید کوتاه‌تر باشد، تغییر حفظ می‌شود.
4. فرایند تا نبود بهبود ادامه پیدا می‌کند.

در این معماری:

• ACO مناطق مناسب فضای جست‌وجو را پیدا می‌کند.
• Local Search هر جواب را در همان ناحیه بهبود می‌دهد.

این ترکیب اغلب از ACO ساده نتیجه بهتری می‌دهد، اما هزینه محاسباتی را افزایش می‌دهد.

تفاوت ACO و الگوریتم ژنتیک

برای جزئیات بیشتر، مقاله الگوریتم ژنتیک چیست؟ را بخوانید.

تفاوت ACO و الگوریتم ازدحام ذرات

برای آشنایی بیشتر، مقاله الگوریتم ازدحام ذرات چیست؟ را مطالعه کنید.

تفاوت ACO و الگوریتم دایکسترا

Dijkstra برای پیدا کردن کوتاه‌ترین مسیر از یک مبدأ در گرافی با وزن‌های غیرمنفی طراحی شده است و در شرایط مشخص جواب دقیق ارائه می‌کند.

ACO یک روش تقریبی برای مسائل پیچیده‌تر و ترکیبی است.

برای پیدا کردن کوتاه‌ترین مسیر ساده میان دو نقطه، استفاده از Dijkstra یا A* معمولاً منطقی‌تر است. ACO زمانی ارزش بررسی دارد که مسئله شامل ترکیب‌های پیچیده، چند مقصد، محدودیت‌های متعدد یا تابع هدف غیرمعمول باشد.

مزایای الگوریتم کلونی مورچگان

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

محدودیت‌های الگوریتم ACO

• تضمینی برای یافتن جواب بهینه ندارد.
• ممکن است دچار همگرایی زودرس شود.
• تنظیم پارامترها می‌تواند دشوار باشد.
• تعداد ارزیابی‌ها ممکن است زیاد شود.
• نگهداری ماتریس فرومون برای گراف بزرگ پرهزینه است.
• برای مسائل پیوسته انتخاب طبیعی اول نیست.
• کیفیت نتیجه به اطلاعات ابتکاری وابسته است.
• عملکرد آن روی مسائل مختلف می‌تواند بسیار متفاوت باشد.

چگونه پارامترهای ACO را تنظیم کنیم؟

مقادیر زیر فقط نقطه شروع آزمایش هستند:

برای انتخاب پارامترها:

1. یک بودجه ارزیابی ثابت تعیین کنید.
2. چند ترکیب پارامتر را آزمایش کنید.
3. هر ترکیب را با چند Seed اجرا کنید.
4. میانگین و پراکندگی نتایج را مقایسه کنید.
5. نتیجه را با الگوریتم‌های پایه بسنجید.

چه زمانی از الگوریتم کلونی مورچگان استفاده کنیم؟

ACO زمانی گزینه مناسبی است که:

• مسئله گسسته یا ترکیبی باشد.
• جواب به‌صورت یک مسیر یا ترتیب ساخته شود.
• اطلاعات ابتکاری مفیدی وجود داشته باشد.
• بررسی تمام جواب‌ها امکان‌پذیر نباشد.
• یک جواب بسیار خوب کافی باشد.
• ارزیابی جواب‌ها امکان اجرای موازی داشته باشد.
• ساختار مسئله در طول زمان تغییر کند.

احتمالاً انتخاب مناسبی نیست اگر:

• الگوریتم دقیق و سریع برای مسئله وجود دارد.
• مسئله فقط یک کوتاه‌ترین مسیر ساده است.
• متغیرها کاملاً پیوسته‌اند.
• تعداد گره‌ها آن‌قدر زیاد است که ماتریس فرومون قابل نگهداری نیست.
• هر ارزیابی بسیار پرهزینه است.
• تضمین ریاضی برای جواب بهینه لازم است.

اشتباهات رایج در پیاده‌سازی ACO

حذف‌نکردن گزینه‌های نامعتبر

مورچه نباید بتواند یک شهر را در TSP چند بار انتخاب کند یا وارد مرحله غیرمجاز گردش‌کار شود.

تبخیر بسیار کم

فرومون‌های اولیه برای مدت طولانی باقی می‌مانند و مسیرهای قدیمی بیش‌ازحد اثرگذار می‌شوند.

تبخیر بسیار زیاد

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

Beta بسیار بزرگ

مورچه‌ها فقط گزینه محلی و کوتاه‌تر را انتخاب می‌کنند و امکان کشف مسیرهای بهتر کاهش می‌یابد.

Alpha بسیار بزرگ

مورچه‌ها خیلی سریع از مسیر محبوب پیروی می‌کنند و تنوع از بین می‌رود.

ارزیابی تنها یک اجرا

ACO تصادفی است و نتیجه یک Seed برای مقایسه الگوریتم‌ها کافی نیست.

مقایسه‌نکردن با روش پایه

نتیجه باید حداقل با یک روش حریصانه، Random Search یا الگوریتم استاندارد مسئله مقایسه شود.

نادیده‌گرفتن هزینه API

اگر هر مسیر شامل چند فراخوانی مدل باشد، باید بودجه ارزیابی پیش از اجرا محاسبه شود.

پرسش‌های متداول

ACO مخفف چیست؟

ACO مخفف Ant Colony Optimization و به معنای الگوریتم بهینه‌سازی کلونی مورچگان است.

الگوریتم مورچگان به زبان ساده چیست؟

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

فرومون در الگوریتم ACO چیست؟

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

آیا ACO نوعی هوش مصنوعی است؟

ACO یکی از روش‌های هوش ازدحامی و بهینه‌سازی فراابتکاری است و در بسیاری از مسائل هوش مصنوعی، تحقیق در عملیات و علوم کامپیوتر استفاده می‌شود.

آیا الگوریتم مورچگان بهترین مسیر را تضمین می‌کند؟

خیر. ACO معمولاً به‌دنبال جواب مناسب است و تضمینی برای یافتن بهترین جواب سراسری ندارد.

بهترین کاربرد ACO چیست؟

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

آیا ACO برای متغیرهای پیوسته مناسب است؟

نسخه کلاسیک ACO بیشتر برای مسائل گسسته طراحی شده است. نسخه‌هایی برای فضای پیوسته وجود دارند، اما PSO، Differential Evolution یا روش‌های گرادیانی ممکن است انتخاب طبیعی‌تری باشند.

آیا می‌توان ACO را به مدل‌های هوش مصنوعی متصل کرد؟

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

آیا API درواره با ACO قابل‌استفاده است؟

بله. مسیرهای ساخته‌شده توسط مورچه‌ها می‌توانند با مدل‌های مختلف از طریق API درواره اجرا و ارزیابی شوند. بهتر است پاسخ‌ها Cache و تعداد درخواست‌ها محدود شود.

جمع‌بندی

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

مهم‌ترین اجزای ACO عبارت‌اند از:

1. مورچه‌های مصنوعی
2. ماتریس فرومون
3. اطلاعات ابتکاری
4. انتخاب احتمالی
5. تبخیر فرومون
6. تقویت جواب‌های مناسب
7. ذخیره بهترین جواب

برای استفاده صحیح از ACO باید:

1. نمایش مناسبی برای جواب طراحی کنید.
2. گزینه‌های نامعتبر را از ابتدا حذف کنید.
3. تابع هدف را با مسئله واقعی هماهنگ کنید.
4. میان اکتشاف و بهره‌برداری تعادل ایجاد کنید.
5. نرخ تبخیر را آزمایش کنید.
6. چند اجرای مستقل انجام دهید.
7. نتیجه را با روش‌های پایه مقایسه کنید.
8. هزینه ارزیابی را کنترل کنید.
9. در صورت نیاز ACO را با جست‌وجوی محلی ترکیب کنید.

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

برای اتصال برنامه خود به مدل‌های مختلف می‌توانید از مستندات API درواره شروع کنید.

آدرس پایه API درواره:

https://api.darvareh.ir/v1

API درواره با ساختار OpenAI سازگار است و امکان دسترسی یکپارچه به مدل‌های مختلف را برای توسعه‌دهندگان و کسب‌وکارهای ایرانی فراهم می‌کند.

مقالات مرتبط

• الگوریتم ژنتیک چیست؟
• الگوریتم ازدحام ذرات چیست؟
• یادگیری ماشین چیست؟
• یادگیری بدون نظارت، K-Means و PCA
• ارزیابی مدل‌های هوش مصنوعی و Evals
• مسیریابی هوشمند میان مدل‌های هوش مصنوعی
• معماری چندمدلی و چندارائه‌دهنده
• راهنمای API سازگار با OpenAI

منابع

• Ant Colony Optimization نوشته Dorigo و Stützle
• Ant Colony Optimization: A New Meta-Heuristic
• کتاب Ant Colony Optimization از MIT Press
• Scikit-opt Documentation
• Scikit-opt GitHub Repository
• NetworkX Documentation
• NetworkX Traveling Salesman Problem
• مستندات API درواره

این مقاله صرفاً با هدف آموزش و اطلاع‌رسانی تهیه شده است. پیش از استفاده عملی، مستندات رسمی سرویس‌ها و صفحه سلب مسئولیت را مطالعه کنید.