## 3 Problem Formulation
### Service Composition under Multi-Cloud  
Firstly, we need to introduce the basic process of cloud service composition. The process of cloud service composition is shown in Figure 1 and can be decomposed into three stages:  
1. Requirements decomposition: a complex requirement is decomposed into several subtasks, all of which constitute a composite task. A subtask can be completed by a cloud service;
2. Service selection: a search is conducted for services in the cloud service data center that match the functional requirements of each subtask, and these services are aggregated to form a candidate service set;Service composition: an algorithm is used to select appropriate cloud services from the pre-selected candidate service set for each subtask and combine them to form a final cloud service composition plan. However, in our study, the focus is on cloud service composition within a multi-cloud environment. A multi-cloud environment (MCE) consists of multiple clouds, each containing a set of cloud service classes that include multiple cloud services with similar functionality yet varying non-functional attributes. All cloud service information within the cloud environment is registered in the cloud service data center. Users submit requests via a web application or mobile application. When the composition agent receives a user's request, it first decomposes the request into multiple subtasks. The agent then selects appropriate cloud services for each subtask from the cloud service data center to create a candidate cloud service set. Finally, an algorithm is employed to select the most suitable cloud services from the candidate service set, resulting in the formation of a comprehensive cloud service composition plan. The results are subsequently returned to the user. Figure 2 illustrates an example of this process, in which there are two clouds, \(cd_{1}\) and \(cd_{2}\), with three service classes in \(cd_{1}\), each containing multiple cloud services with varying non-functional attributes. The composition agent serves as an intermediary, responsible for receiving user requests, searching for matching cloud services amongst the service pool, and using an algorithm to combine the identified cloud services, ultimately returning the cloud service composition results to the user. Figure 1: Cloud service composition framework. We use \(MCECSC=\{Task,CD,P,W,Cons\}\) to represent cloud service composition in a multi-cloud environment, where the meanings of the symbols are as follows:  
1. \(Task=\{T_{1},T_{2},\cdots\cdots,T_{n}\}\) represents a collection of subtasks. \(T_{i}(i=1,2,\cdots\cdots,n)\) refers to the \(i\)-th subtask, and \(n\) signifies the total number of subtasks. These subtasks collectively form the user's intricate requirement. While a subtask can be completed by one or multiple cloud services, typically, one cloud service is sufficient for completing a single subtask;
2. \(CD=\{cd_{1},cd_{2},\cdots\cdots,cd_{k}\}\) signifies a group of clouds, with \(cd_{j}\)\((j=1,2,\cdots\cdots,k)\) signifying the \(j\)-th cloud in the environment, and \(k\) representing the number of clouds in the multi-cloud setting. A cloud usually contains various service classes, also referred to as abstract services. The definition of a cloud can be summarized as follows: \[cd_{j}=\left\{S_{1}^{j},S_{2}^{j},\cdots\cdots,S_{m}^{j}\right\}\] where \(S_{l}^{j}(l=1,2,\cdots\cdots,m)\) represents the \(l\)-th service class in the \(j\)-th cloud, with \(m\) representing the number of service classes in the \(j\)-th cloud. A service class is a set of cloud services that cater to the requirements, possessing similar functionality yet varying non-functional attributes. The definition of a service class is as follows: \[S_{l}^{j}=\left\{cs_{l,1}^{j},cs_{l,2}^{j},\cdots\cdots,cs_{l,c}^{j}\right\}\] where \(cs_{l,i}^{j}(i=1,2,\cdots\cdots,c)\) represents the \(i\)-th specific service in the \(l\)-th service class in the \(j\)-th cloud, with \(c\) representing the number of cloud services in the service class.