BÀI TOÁN NGƯỜI BÁN HÀNG

     
Thuật toán đổi mới Ant Colony Thuật toán Ant Colony bài toán người bán sản phẩm Ứng dụng thuật toán ACO quản lý chi phí dự án công trình xây dựng


Bạn đang xem: Bài toán người bán hàng

*
pdf

cấu hình thiết lập tuyến đường cất cánh khép kín đáo của vật dụng thể cất cánh không người lái xe hạng vơi khi có dữ liệu thống kê về gió vào vùng ba...




Xem thêm: Nội Dung Dạy Học Là Gì - Nội Dung Dạy Học By Tàn Độc

*
6
*
0
*
3


Xem thêm: How Is Your Neighborhood? What Is Your Neighborhood Like

Nội dung

gmail.com 121. Giới thiệuLý thuyết về thuật toán Ant Colony cùng ứngdụng thuật toán đã được rất nhiều tác giả trongvà không tính nước nghiên cứu. Những tác giả MarcoDorigo, Thomas Stützle nghỉ ngơi trường đh TheMIT Press Cambridge, Massachusetts Londonđã đưa ra biện pháp tiếp cận và định hướng để ứng dụngthuật toán Ant Colony vào câu hỏi người bánhàng (TSP) <1>. Trong bài báo của tác giả PhạmHồng Luân cùng Dương Thành Nhân, Tạp chíPhát triển khoa học và technology (Journal ofScience and Technology Development), ISSN:1859-0128 đã giới thiệu thuật toán Ant Colony vàứng dụng thuật toán vào cai quản chi giá tiền dự ánxây dựng <2>. Rất có thể nói, phân tích lý thuyếtvề thuật toán Ant Colony đã siêu hoàn thiện. Bàibáo này đề xuất một cách cải tiến thuật toán AntColony để có thể tìm được đường đi ngắn hơnđường đi nhưng thuật toán Ant Colony tìm kiếm ra.Ngoài phần ra mắt và lịch sử nghiên cứucủa vấn đề ở chỗ 1, phần 2 sẽ trình bày về bàitoán người bán hàng và những giải thuật giải quyếtbài toán. Phần 3 trình cách đổi mới thuật toán AntColony. Kết quả nghiên cứu và tóm lại sẽ là nộidung của phần 4.và khoảng cách giữa hai thành phố bất kì vẫn biếttrước thì đường đi ngắn nhất nhưng mà người phân phối hàngcó thể triển khai được làm thế nào để cho đi hết toàn bộ cácthành phố, mỗi thành phố một lần để trở lại lạithành phố A lúc đầu là như vậy nào?Bài toán này được lời khuyên giải quyết vào thếkỷ sản phẩm công nghệ XVII vị hai công ty toán học fan Anh là SirWilliam Rowan Hamilton cùng Thomas PenyngtonKirkman, với được ghi chép trong giáo trình Lýthuyết vật thị lừng danh của Oxford. Kế tiếp bàitoán trở thành vấn đề khó thách thức toàn thểcác đơn vị toán học cùng tin học trên nhân loại bởi độphức tạp thuật toán tăng theo hàm số mũ (thuộclớp việc NP-khó).Các bên khoa học bước đầu tiếp cận bài toán,dùng máy tính xách tay thử nghiệm thống kê giám sát và công bốcác kết quả giải việc này từ năm 1954 cùng với sốthành phố là 49, với năm 2004 việc giải đượcvới số tp là 24.978, và số lượng thànhphố càng ngày càng tăng cao <3>.2. Việc người bán sản phẩm (TSP) và các giảithuật giải quyết bài toán2.1 việc người bán sản phẩm (TravelingSalesman Problem)Bài toán yêu mong tìm đường đi ngắn độc nhất vô nhị chonhân viên bán sản phẩm (traveling salesman), nhânviên bán sản phẩm xuất phát xuất phát điểm từ 1 thành phố, đi qualần lượt toàn bộ các tp có trong lộ trình duynhất một đợt và trở lại thành phố thuở đầu vớichi tổn phí thấp nhất.Ví dụ ngơi nghỉ Hình 1 việc yêu mong tìm con đường đingắn nhất đến người bán hàng xuất phát từ thànhphố A và phải đi qua toàn bộ các tp B,C,Dsau đó trở lại thành phố A, toàn bộ các thành phốđều có lối đi đến các thành phố còn lại.Nếu người bán hàng xuất phân phát từ thành phố A,Hình 1. Việc người phân phối hàng2.2 lời giải Ant ColonyBài toán người bán sản phẩm hoàn toàn hoàn toàn có thể giảibằng giải thuật Ant Colony, thuật toán này còn có thểáp dụng cho những lớp bài toán. Để hoàn toàn có thể hiểuhơn về thuật toán này bạn có thể tìm hiểuđặc điểm chuyển động trong tự nhiên của bọn kiếnvà trường đoản cú đó rất có thể hiểu rộng về thuật toán Ant Colony.Trong tự nhiên loại kiến chuyển động theo quyluật sau: lúc tìm tìm thức ăn, trong vượt trình 13di đưa kiến thường vướng lại mùi riêng rẽ của nóđể các con con kiến trong bọn có thể thừa nhận diện ra lốidi gửi của chúng, hương thơm của kiến để lại trênđường đi này được gọi là pheromone. Đây là yếutố giúp bọn kiến ghi lại và trao đổi thông tinvới nhau khi chúng đi tìm kiếm nguồn thức ăn. Lúc tìmthấy mối cung cấp thức ăn, mỗi nhỏ kiến sẽ dịch rời từtổ tới nơi gồm nguồn thức ăn uống theo đường đi đã tìmthấy. Trường đoản cú tổ kiến đến nơi tất cả thức ăn sẽ sở hữu được nhiềuđường đi. Vì thế thuở đầu các chú kiến đã đi ngẫunhiên theo các con mặt đường từ điểm xuất xứ đếnđích. Tuy nhiên, sau một thời hạn di chuyểnnhất định, những chú kiến trong đàn sẽ tìm thấy đượcđường đi ngắn tốt nhất từ tổ tới nguồn thức ăn. Saukhi quan cạnh bên và nghiên cứu hoạt động vui chơi của đànkiến vào tự nhiên, họ nhận thấy rằng quátrình tìm lối đi ngắn độc nhất từ tổ tới mối cung cấp thứcăn dựa trên các quy chính sách sau:Khi dịch chuyển kiến sẽ dùng phoremone đểđánh dấu và trao đổi tin tức với nhau nhằmtìm ra đường đi ngắn tốt nhất từ tổ cho nguồn thứcăn, đồng thời trong quá trình di chuyển đó chúngđể lại một lượng hương thơm (phoremone) bên trên đườngchúng dịch rời qua.Các nhỏ kiến đi sau sẽ phụ thuộc vào lượng mùimà những con con kiến đi trước giữ lại để tiến hành tìmđường đi đến mình, khi trên đường đi chưa cómùi vướng lại thì chúng di chuyển một cách ngẫunhiên, lượng mùi nhằm lại trê tuyến phố đi của cáccon kiến dịch rời trước cũng bị bay tương đối theothời gian.Đường đi nào có lượng thông tin mùi nhằm lạicàng nhiều thì xác suất được những con con kiến chọncàng cao, ngược lại đường đi tất cả lượng mùi thấpthì phần trăm chọn càng thấp.Qua một quá trình di chuyển đàn kiến sẽ chọnđược cho khách hàng một đường đi ngắn tuyệt nhất từ tổ đếnnguồn thức ăn.Dựa vào cơ chế hoạt động của đàn kiến trongtự nhiên cơ mà thuật toán Ant Colony đã ra đời.Thuật toán Ant Colony mô phỏng chuyển động củađàn kiến nhân tạo như sau: Thuật toán sử dụngmột đàn kiến tự tạo (Artificial Ants) nhằm môphỏng lại các hoạt động trong tự nhiên và thoải mái của đànkiến. Đàn kiến nhân tạo có một số trong những điều chỉnh vềmặt hoạt động so với bọn kiến tự nhiên và thoải mái nhằmtăng tính tác dụng của thuật toán. Giải thuật nàychủ yếu mô tả hoạt động tìm đường đi ngắn nhấtcủa các con con kiến nhân tạo dựa vào lượng mùi đểlại trong quá trình di chuyển của bầy kiến. Núm thểvề vận động của lũ kiến tự tạo được trìnhbày như sau: cho 1 đồ thị khá đầy đủ gồm những đỉnhvà cạnh trong những số đó đỉnh là địa điểm kiến sẽ đi qua và cáccạnh là những đoạn đường. Nút thuở đầu cho đườngđi của mỗi bé kiến được chọn 1 cách ngẫunhiên và thông tin mùi (pheromone) được tínhtoán và bỏ trên mỗi đoạn đường. Mỗi bé kiếnsẽ chọn đường đi theo những nguyên tắc:+ phụ thuộc thông tin mùi để lại sở hữu trên cácđoạn con đường để tính phần trăm chọn đoạn đườngtiếp theo và làm lối đi cho nhỏ kiến.+ Đường đi tất cả lượng mùi (pheromone) nhiềuhơn thì sẽ tiến hành gán một tỷ lệ lớn hơn. Ngượclại những đoạn đường đi có lượng tin tức mùithấp hơn đang có tỷ lệ được chọn thấp hơn. Conkiến đã tìm con đường đi tính đến khi hoàn thành mộtđường đi của nó (thỏa mãn điều kiện dừng củacon kiến).+ Một mặt đường đi tương đối đầy đủ và hoàn hảo đượcgọi là một trong lời giải đúng cho bài toán đặt ra. Cácđường đi tìm kiếm được sẽ tiến hành phân tích, so sánh vàđánh giá để tìm phương án tối ưu nhất tất cả thể. Đólà lời giải tối ưu của bài toán.+ sau thời điểm tất cả loài kiến trong đàn hoàn thànhviệc tìm lối đi của nó, ta sẽ tiến hành cập nhậtthông tin mùi cho các cung. Con số của mùi sẽđược tính toán và kiểm soát và điều chỉnh để tìm kiếm được phươngán về tối ưu tốt hơn:• Các giải thuật có đường đi ngắn lại hơn nữa sẽ gồm khốilượng pheromone lớn hơn để bỏ lên các cungđã được đi qua. Ngược lại, các lời giải cho đườngđi dài hơn nữa sẽ có khối lượng pheromone bé nhỏ hơn.• bé kiến đang chọn lối đi có lượng mùi lớnhơn và tỷ lệ chọn đường đi này cũng cao hơn. 14Quá trình này được lặp đi lặp lại cho tới khi hầuhết các con loài kiến trong bọn kiến nhân tạo chọncùng một con đường đi, với đây chính là lời giải củabài toán.nhận ra hai phần đường đi giao nhau với tiến hànhthực hiện sa thải những phần đường đi giao nhauđó để tạo thành một chu trình mới tất cả độ dài ngắnhơn quy trình mà thuật toán Ant Colony vẫn tìm ra.THUẬT TOÁN ANT COLONYInput: Số kiến, khởi sản xuất số thànhphố, vị trí tọa độ những thành phố,điểm xuất phát, khởi sản xuất mùi.Output: Chu trình đường đi ngắnnhất từ tp xuất phát qua cácthành phố sót lại một lần và quayvề lại thành phố ban đầuMethod:Begin:B1:Nhập tài liệu đầu vào: số kiến,vị trí tọa độ những thành phố,khoảng bí quyết giữa các thành phố,điểm xuất phát, khởi chế tác mùi.Hình 2. Chu trình có giảm nhau và quy trình cải tiếnChẳng hạn, cùng với một hành trình đi bao gồm giao nhaunhư Hình 2 là ABCD, cửa hàng chúng tôi tiến hành loại bỏnhững phần đường đi giao nhau để tạo ra chu trìnhmới là ACBD có độ dài ngắn hơn.Ý tưởng của thuật toán cách tân được mô tảrõ hơn hẳn như là sau: mang sử người bán hàng cần dichuyển theo chu trình ABCDA. Nhưvậy theo hình 2.1, ta thấy tổng chiều nhiều năm chu trìnhngười đó cần di chuyển là AB+BC+CD+DA.B2: Xây dựng cách thực hiện lựa chọnđường điB3: update mùiB4: ví như chu trình lối đi làngắn độc nhất vô nhị thì qua B5 ngược lạithì trở lại B2End3. Giải pháp cải tiến thuật toán Ant ColonyTrong quá trình xem xét và mày mò về giảithuật Ant Colony cho việc người buôn bán hàng,chúng tôi đề ra vấn đề liệu rằng có cách nào đểcải tiến thuật toán Ant Colony để lối đi tìmđược của các con loài kiến trong thuật toán ngắn hơnkhông?Qua một quá trình xem xét và tò mò chúngtôi nhận ra rằng bên trên chu trình lối đi mà thuậttoán Ant Colony tìm kiếm được có số đông đoạn đườngđi giao nhau, phụ thuộc đó chúng tôi có thể làmcho các đoạn lối đi này ngắn thêm bằng cáchkhông lựa chọn những đoạn đường đi giao nhautrong quy trình đường đi kiếm ra được tạo ra bởithuật toán Ant Colony đó.Chúng tôi đã phụ thuộc toán học nhằm tìm cáchHình 2.1Trong chu trình dịch chuyển ta thấy bao gồm hai đoạnđường giao nhau là BC và DA.Việc người bán hàng di chuyển hẳn sang hai đoạnđường này do người bán sản phẩm phải di chuyểntheo chu trình ABCDA. Để làm chochu trình dịch chuyển của người bán sản phẩm ngắnhơn nhóm shop chúng tôi đề xuất người bán sản phẩm dichuyển theo chu trình ABDCA. Việcnày làm cho đường đi của quy trình di chuyểnsẽ ngắn thêm một đoạn vì theo toán học tập ta thấy đoạn đườngAC+BD