رتبه موضوع:
  • 0 رای - 0 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5
حل مسئله جورچین با الگوریتم ژنتیک
#1
با سلام و تشکر از زحمات دوستان
یکی از مسائلی که کمتر به آن پرداخته شده حل مسئله جورچین با الگوریتم ژنتیک است. لطفا اگر ممکن است در این مورد راهنمایی کنید و کد زبان C آن را ارائه کنید. سوال کردن
پاسخ
سپاس شده توسط
#2
با سلام خدمت شما دوست عزیز

 چند سورس همراه با آموزش ضمیمه کردم امیدوارم مفید بوده باشه

سورس های به عنوان زبان های برنامه نویسی و به تعداد زیاد و روش های متفاوت دارم کم کم ضمیمه میکنم


مثل حالت خطی 8puzzle  یا..
کد:
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>


typedef char puzzle_t[3][3];

puzzle_t _puzzle_start = { {1, 2, 3},
               {4, 5, 6},
               {7, 8, 0}
            };
puzzle_t _puzzle_stop =    {  {1, 2, 3},
               {4, 0, 5},
               {6, 7, 8}
            };
struct    context_t {
    std::list<puzzle_t*> abort_states;
    std::list<std::string> solution;
    int max_depth;
};


std::ostream& operator<<(std::ostream &s, const puzzle_t &p)
{
    for (int y=0; y<3; ++y)    {
        for (int x=0; x<3; ++x)    {
            s << (int)p[y][x] << " ";
        }
        s << std::endl;
    }
    return s;
}

bool solver_rec(puzzle_t& start, const puzzle_t& stop, int y0, int x0, int depth, context_t &ctx)
{
    // enough CPU cycles wasted
    if (depth >= ctx.max_depth) return false;

    // is the actual start a abort state?
    for (std::list<puzzle_t*>::iterator it = ctx.abort_states.begin(); it != ctx.abort_states.end(); ++it)    {
        bool abort = true;
        for (int y=0; y<3; ++y)    {
            for (int x=0; x<3; ++x)    {
                if (start[y][x] != (**it)[y][x]) abort=false;
            }
        }
        // this state will be checked by on of the parents, anyhow
        if (abort)    {
            return false;
        }
    }
    
    // are we done?
    bool done = true;
    for (int yy=0; yy<3; ++yy)    {
        for (int xx=0; xx<3; ++xx)    {
            if (start[yy][xx] != stop[yy][xx]) done= false;
        }
    }
    if (done) return true;

    // add this state to the list of abort states
    // it safe to push_front an stack objectpointer
    // as we remove it again before stack is unwinded
    // or never ever touch it again
    puzzle_t p;
    memcpy(p, start, sizeof(p));
    ctx.abort_states.push_front(&p);

    for (int yy=0; yy<3; ++yy)    {
        for (int xx=0; xx<3; ++xx)    {
            // if the move is possible, take it
            if (((yy+1 == y0) || (yy-1 == y0)) && (xx == x0))    {
                std::swap(start[yy][xx], start[y0][xx]);
                if (solver_rec(start, stop, yy, x0, depth+1, ctx))    {
                    std::stringstream s;
                    s << depth << ". tile  " << yy << "/" << x0;
                    ctx.solution.push_back(s.str());
                    return true;
                }
                std::swap(start[yy][xx], start[y0][xx]);
            }
            if (((xx+1 == x0) || (xx-1 == x0)) && (yy == y0))    {
                std::swap(start[yy][x0], start[yy][xx]);
                if (solver_rec(start, stop, y0, xx, depth+1, ctx))    {
                    std::stringstream s;
                    s << depth << ". tile " << y0 << "/" << xx;
                    ctx.solution.push_back(s.str());
                    return true;
                }
                std::swap(start[yy][x0], start[yy][xx]);
            }
        }
    }
    // remove the abort state
    ctx.abort_states.pop_front();
    return false;
};

bool solver(puzzle_t& start, const puzzle_t& stop, int max_depth)    
{
    context_t ctx;
    
    // search for the 0 element
    int y0=-1, x0=-1;
    for (int y=0; y<3; ++y)    {
        for (int x=0; x<3; ++x)    {
            if (start[y][x] == 0) {
                y0 = y;
                x0 = x;
                break;
            }
        }
    }
    assert(y0 != -1);
    assert(x0 != -1);
    // breath first search, assures that a shortest solution is found
    for (ctx.max_depth=0; ctx.max_depth<max_depth; ++(ctx.max_depth))    {
        if (solver_rec(start, stop, y0, x0, 1, ctx))    {
            std::cout << "---SOLUTION---" << std::endl;
            for (std::list<std::string>::reverse_iterator it = ctx.solution.rbegin(); it != ctx.solution.rend(); ++it)    {
                std::cout << *it << std::endl;
            }
            return true;
        }
    }
    return false;
}

int main(int argc, char**argv)    
{
    // 3 argument == max_depth
    if (!solver(_puzzle_start, _puzzle_stop, 20))    {
        std::cout << "--- NO SOLUTION ---" << std::endl;
    }
    return 0;
}

این لینک امیدوارم مفید باشه

http://www.markjasmith.com/gen_8_puzzle_solver.shtml
موفق باشید


فایل‌های پیوست
.zip   Moamaye-Hasht.zip (اندازه 221.12 KB / تعداد دانلود: 126)
.zip   MiniPuzzle.zip (اندازه 56.01 KB / تعداد دانلود: 84)
.zip   Puzzle-in-VB.zip (اندازه 11.07 KB / تعداد دانلود: 69)
.pdf   8puzzle.pdf (اندازه 93.26 KB / تعداد دانلود: 146)
.zip   puzzle.zip (اندازه 2.33 KB / تعداد دانلود: 53)
[عکس: <a href=www.Mojsazan.com.gif]" class="mycode_img" />
پاسخ
سپاس شده توسط مهدی ابراهیمی
#3
برای الگوریتم ژنتیک سورس زیر را ضمیمه میکنم امیدوارم مفید باشه

یک سایت مفید
http://www.8puzzle.com/


فایل‌های پیوست
.zip   Solving 8-puzzle Problem Using Genetic Algorithm-Ramin.S.Kalan.zip (اندازه 3.42 KB / تعداد دانلود: 56)
[عکس: <a href=www.Mojsazan.com.gif]" class="mycode_img" />
پاسخ
سپاس شده توسط مهدی ابراهیمی
#4
خیلی از شما متشکرم
لطفاً در صورت امکان در مورد تابع fitness فضای فنوتایپی و ژنوتایپی و representation وعملگرهای بازترکیب و پرش بکاررفته در این مسئله توضیحی هم بفرمایید.من خودم هم جستجوهایی انجام دادم ولی توضیحی پیدا نکردم. لطفا راهنمایی بفرمایید.
با تشکر
پاسخ
سپاس شده توسط


موضوعات مشابه ...
موضوع نویسنده پاسخ بازدید آخرین ارسال
  الگوریتم ژنتیک(Genetic Algorithm) TinaSefati 7 18,237 07-14-2017, 03:12 PM
آخرین ارسال: maryam_f123
  مسئله کشیش و آدم خوار ها & مسئله های مشابه مهرداد عباسی 1 4,686 04-01-2014, 05:53 PM
آخرین ارسال: مهرداد عباسی
  سورس کد و آموزش های الگوریتم کلونی مورچه ها(Ant Colony Algorithm) مهرداد عباسی 31 68,542 01-25-2014, 02:36 PM
آخرین ارسال: najafi123
  مسئله فروشنده دوره‌گرد(Travelling salesman problem، به‌اختصار: TSP ) مهدی ابراهیمی 5 12,401 10-29-2013, 08:34 PM
آخرین ارسال: zooroo
Smile الگوریتم های دوز بازی laleh62 0 3,499 10-04-2013, 06:14 PM
آخرین ارسال: laleh62
  پیاده سازی مسئله 8 وزیر با استفاده از الگوریتم ABC sharokh 2 8,099 12-10-2012, 05:20 PM
آخرین ارسال: FATEMEH1369
  سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C مهرداد عباسی 18 50,154 11-23-2012, 10:21 AM
آخرین ارسال: مهدی ابراهیمی
  الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm مهدی ابراهیمی 6 21,854 05-23-2012, 09:54 PM
آخرین ارسال: مهدی ابراهیمی

پرش به انجمن:


کاربران در حال بازدید این موضوع: 1 مهمان