螞蟻族群演算法於電影拍攝排程之應用

Abstract

在製作與拍攝影片過程中，預算的掌控為最重要的問題之一，本論文主要是探討其中之拍攝排程問題。而在拍攝影片過程中，由於每個場景所需要的演員都不盡相同，因此拍攝的場景跟演員相互之間會有很大的關聯，使得場景的拍攝循序會影響到演員的滯留天數以及總拍攝天數。 在本研究中，我們主要是在探討透過所上述的條件之下，如何做到場景的安排以及演員的排班兩方面的成本能減至最少。在演員排班問題中，我們試著要找出一個場景的拍攝順序能夠使得演員的滯留成本最小化，而這個問題已經被證明是一件很難的問題(NP-hard)。 論文是主要利用螞蟻演算法(Ant Colony Optimization Algorithm, ACO)、將問題的模型推廣至包含單日作業時間的限制，而這項條件會限制住每個拍攝天當中所有拍攝場景的總時數。在每個拍攝計畫當中，所需要的成本包含了所有演員的滯留成本以及單日運作所需要的固定成本，而拍攝天數的最小化也可視為一個裝箱問題，在使用啟發式演算法之一將場景安排到不同的拍攝天內以求得問題初始解，並且再以此解去作後續的改善。

In film production, budgeting is one of the most important issues. In this study, we present the cost minimization issue in talent scheduling and scene scheduling. We determine the sequence of the scenes of shooting days so that the total hold cost of actors can be minimized. We also concern about the daily working capacity, which defines the total duration of scenes allocated in a single day. Our objective function is the total hold cost of all actors’ hold cost and the total operating cost of the active shootings days. This problem is already known to be strongly NP-hard and computationally challenging. In this thesis, we propose an algorithm based upon Ant Colony Optimization (ACO) to solve the scheduling problem. We examine the computational results of our ACO algorithm by using different parameter settings. The computational experiments reveal that the ACO algorithm is more effective and more efficient in obtaining near-optimal solutions.